FFT
问题：
设 \(A(x)=\sum_{i=0}^n a_ix^i\)，\(B(x)=\sum_{i=0}^m b_ix^i\)。求 \(A(x)\) 和 \(B(x)\) 的卷积。
有一个结论：坐标系中 \(n\) 个点确定一个 \(n-1\) 次函数。
可以这样理解：\(n-1\) 次函数有 \(n\) 个系数，而 \(n\) 个点相当于 \(n\) 个方程。
于是我们可以换一种思路求卷积：将 \(n+m+1\) 个不同的 \(x\) 代入多项式，那么其卷积的结果的函数 \(C(x)\) 必然经过 （\(x_i,A(x_i)B(x_i)\)），于是再通过插值就可以得到卷积结果了。
但是，这样子复杂度仍然不变，那该怎么办呢？
于是我们考虑用复数解决问题，在一个单位圆上，圆上的点表示 \(z=\cos\theta+i\sin\theta\)（\(0\le \theta< 2\pi\)）。然后我们把圆分成 \(n\) 等份，便有了单位根：\(w_n^k=\cos{\frac{2\pi k}{n}}+i\sin{\frac{2\pi k}{n}}\)，它有很好的性质：
1.\(w_n^a\times w_n^b=w_n^{a+b}\)，其实就是积化和差直接推式子就可以证了，并且也可以通过这个简单推出 \((w_n^a)^b=w_n^{ab}\)。不过这个式子其实是最最最重要的，也是唯一用到虚数的性质。
2.\(w_n^{k+\frac{n}{2}}=-w_n^k\)，学过三角函数就会发现很显然。
3.\(w_n^{2k}=w_{\frac{n}{2}}^k\)，显然。
4.\(w_n^k=w^{k+n}\)，显然。
然后，考虑如何快速计算多项式的值，通过思考可以得到：
\[\begin{align} A(x)&=a_0+a_1x^1+\cdots+a_{n-1}x^{n-1}+a_nx^n \\ &=(a_0+a_2x^2+\cdots+a_{n-2}x^{n-2})+(a_1+a_3x^2+\cdots+a_{n-1}x^{n-2})x\\ &=A_1(x^2)+A_2(x^2)x\end{align} \]注意：\(A_1(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{\frac{n}{2}-1}\)，\(A_2\) 同理可推，然后在 FFT 中我们规定 \(n=2^{i\in \mathbb {Z}}\)，并且我们在运算中是不会管第 \(n\) 项的，故 \(n\) 必须大于多项式的次数。
但是这并不能优化我们的复杂度，于是我认为 FFT 一个很厉害的地方来了，我们将单位根 \(w_n^0,w_n^1,\cdots,w_n^{n-1}\) 分带入多项式并求值，那么：
\(A(w_n^k)=A_1(w_{\frac{n}{2}}^k)+w_n^kA_2(w_{\frac{n}{2}}^k)\) (\(0\le k < \frac{n}{2}\))
\(A(w_n^k)=A_1(w_{\frac{n}{2}}^k)-w_n^kA_2(w_{\frac{n}{2}}^k)\) (\(\frac{n}{2}\le k <n\))
这样，我们就有了较大的突破，因为这样子，我们要求的东西就是可转移的了，它就相当于一个 \(f(n)=f_1(n)+k\times f_2(n)\)，于是，要求它每一项的值就可以通过递归实现了，为了更好的理解这里给出代码:
void FFT (int lim, comp F[])
{
if (lim == 1) return ;
comp F1[lim >> 1], F2[lim >> 1];
rep (i, 0, (lim >> 1) - 1) F1[i] = F[i << 1], F2[i] = F[i << 1 | 1];
FFT (lim >> 1, F1), FFT (lim >> 1, F2);
comp w = (comp) {1, 0};
comp wk = (comp) {cos (2.0 * PI / lim), sin (2.0 * PI / lim)};
for (int i = 0; i < (lim >> 1); ++ i, w = w * wk)
{
F[i] = F1[i] + F2[i] * w;
F[i + (lim >> 1)] = F1[i] - F2[i] * w;
}
}
我认为仔细看是可以看懂的，首先我们把系数带进自己的左右节点的数组，然后我们发现每一层完成以后自己的数组变成了每一个 \(F(w_n^k)\) 的答案，然后再转移即可。
于是每个需要的 (\(x_i,A(x_i)B(x_i)\)) 便求出来了，然后我们需要考虑如何通过已有坐标推出多项式系数了。
我们设 \(y_i=A(x_i)B(x_i)\)，\(C(x)=\sum_{i=0}^{n-1} y_ix^i\)，然后我们分别将 \(w_n^0,w_n^{-1},\cdots,w_n^{1-n}\) 带入进这个多项式，设其结果为 \(z_0,\cdots,z_{1-n}\)，我们开始求 \(z\)：
\[\begin{align} z_k&=\sum_{i=0}^{n-1}y_i(w_n^{-k})^i\notag\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} a_j(w_n^i)^j(w_n^{-k})^i\notag\\ &= \sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1} (w_n^{j-k})^i\notag\end{align} \]此时，当 \(j=k\) 时，内部求和的值显然为 \(n\)，而当 \(j\neq k\) 时，我们相当于是在求一个等比数列求和，内部求和的值便是 \(\large\frac{(w_n^{j-k})^n-1}{w_n^{j-k}-1}\)，其中可以发现 \((w_n^{j-k})^n\) 就是 \(w_n^0=1\)，于是内部求和的总和就是零，那么可以得出 \(z_k=na_k\) 即 \(a_k=\frac{z_k}{n}\)。于是我们求出 \(w_n^{-k}\) 就可以求出 \(z_k\) 了，现在考虑怎么求：
设 \(w_n^k=\cos\theta+isin\theta\)， 而 \(w_n^{-k}=w^{n-k}\)，所以 \(w_n^{-k}=\cos\theta-i\sin\theta\)，这个东西也可以通过 FFT 求，于是我们就学会了 FFT 了！接下来上的代码：
void FFT (int lim, comp F[], int op)
{
if (lim == 1) return ;
comp F1[lim >> 1], F2[lim >> 1];
rep (i, 0, (lim >> 1) - 1) F1[i] = F[i << 1], F2[i] = F[i << 1 | 1];
FFT (lim >> 1, F1, op), FFT (lim >> 1, F2, op);
comp w = (comp) {1, 0};
comp wk = (comp) {cos (2.0 * PI / lim), sin (2.0 * PI / lim) * op};
for (int i = 0; i < (lim >> 1); ++ i, w = w * wk)
{
F[i] = F1[i] + F2[i] * w;
F[i + (lim >> 1)] = F1[i] - F2[i] * w;
}
}
signed main ()
{
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
n = rd (), m = rd ();
int l = 0;
for (lim = 1; lim <= n + m; lim <<= 1, ++ l) ;
rep (i, 1, lim) R[i] = (R[i >> 1] >> 1) | (i & 1) << (l - 1);
rep (i, 0, n) A[i].x = rd ();
rep (i, 0, m) B[i].x = rd ();
FFT (lim, A, 1), FFT (lim, B, 1);
rep (i, 0, lim) A[i] = A[i] * B[i];
FFT (lim, A, -1);
rep (i, 0, n + m) printf ("%lld ", (int) (A[i].x / lim + 0.5));
}
这里的 \(op\) 就是表示带进去的是 \(w_n^k\) 还是 \(w_n^{-k}\)，然后还有要注意的就是 \(lim\) 其实就是重置成 \(2\) 的次幂的新的 \(n\)，显然对于答案不会产生任何影响，并且复杂度跟线段树一样，\(O(n\log n)\)。
这个写法效率很慢，有一个叫蝴蝶变换的更优秀的规律可以优化它，这里不多赘述。
标签：F1,frac,变换,comp,sum,FFT,傅里叶,lim,快速 From： https://www.cnblogs.com/lalaouyehome/p/18063511