FFT理解
还是得靠理解啊
背景
FFT靠背板的选手被合数循环FFT题卡掉了。
前言
FFT的核心思想是DFT和IDFT.
换言之就是快速求出点值表示。
前置
单位根：
w
w
w:n次方后变成1（乘法单位元）。
要是有
w
n
2
=
−
1
w^\frac{n}{2}=-1
w2n=−1更为舒适(
2
n
F
F
T
2^nFFT
2nFFT时使用)
实现
我们拿一个数组存储当前的对应的点值（废话）。
其中下标对应的是多少次根。
以2的n次方为循环节的fft为例:
如
F
(
x
)
=
a
1
x
n
0
+
a
2
x
n
1
.
.
.
.
.
.
a
n
−
1
x
n
n
−
1
F(x)=a_1x^0_n+a_2x^1_n......a_{n-1}x^{n-1}_n
F(x)=a1xn0+a2xn1......an−1xnn−1
那么
F
(
x
)
=
(
a
1
x
n
/
2
0
+
a
3
x
n
/
2
2
+
.
.
.
.
.
.
.
)
+
x
∗
(
a
2
x
n
/
2
0
+
a
4
x
n
/
2
2
+
.
.
.
.
.
.
.
)
F(x)=(a_1x^0_{n/2}+a_3x^2_{n/2}+.......)+x*(a_2x^0_{n/2}+a_4x^2_{n/2}+.......)
F(x)=(a1xn/20+a3xn/22+.......)+x∗(a2xn/20+a4xn/22+.......)
并且由于
x
n
n
=
=
x
n
/
2
n
/
2
x^n_n==x^{n/2}_{n/2}
xnn==xn/2n/2,因此上面两个值都不用换直接拿来用
大概是这个样子：
原数组:
a
1
(
x
n
/
2
0
)
,
a
2
(
x
n
/
2
0
)
,
a
1
x
n
/
2
1
,
a
2
x
n
/
2
1
.
.
.
.
.
.
a_1(x^0_{n/2}),a2(x^0_{n/2}),a_1x^1_{n/2},a_2x^1_{n/2}......
a1(xn/20),a2(xn/20),a1xn/21,a2xn/21......
求数组:
a
n
(
x
n
0
)
,
a
n
(
x
n
1
)
,
a
n
(
x
n
2
)
a_n(x^0_{n})\ \ ,a_n(x^1_{n})\ \ ,a_n(x^2_{n})
an(xn0) ,an(xn1) ,an(xn2)
由于单位根性质，
a
n
(
x
n
k
)
=
a
1
(
x
n
2
k
)
+
x
n
k
∗
a
2
(
x
n
2
k
)
a_n(x^k_n)=a_1(x^{2k}_n)+x^k_n*a_2(x^{2k}_n)
an(xnk)=a1(xn2k)+xnk∗a2(xn2k),然后会发现如果2k>n变1了，因此每个新位置是由哪些原先的位置求出的呈一个循环，下标每增加1，区间（循环）右移当前分成了几个的长度。
这样做就可以递归分解合数的fft了。
优化
理论上多合数积底的fft也可以和
2
n
2^n
2n底的一样翻转。
但是裸奔的多合数基底fft都是黑题了，你还想优化常数？你以为你谁啊
上面那句话是作者自用的，请勿误伤。