FFT：
首先要知道 \(n\) 次多项式可以用 \(n+1\) 个系数表示，也可以用 \(n+1\) 个不同的 \(x\) 得到的 \(f(x)\) 点值来唯一确定。
那么设单位根 \(\omega_{n}\)，则有 \(f(\omega_{n}^k)=f_0(\omega_{n/2}^k)+\omega_n^kf_1(\omega_{n/2}^k),f(\omega_{n}^{k+n/2})=f_0(\omega_{n/2}^k)-\omega_n^kf_1(\omega_{n/2}^k)\)。
发现只有一个符号的差别，遂可以分治。
然后发现直接递归常数爆炸，考虑每个数按奇偶划分之后会变到哪里，显然是其二进制高低翻转。
于是直接做，IDFT时把 \(\omega_n\) 换成其共轭复数，最后序列整个除掉一个长度即可。
NTT：
发现原根 \(g\) 的性质和单位根有诸多相似之处，且满足所有 FFT 需要的性质，所以可以直接用 \(g^{(p-1)/n}\) 来代替 \(\omega_n\)，用其逆元代替共轭复数即可。最后都要除掉长度。
分治 FFT/NTT：
形如 \(f_{i}=\sum f_{i-j}g_j\) 的，就是 \(f_i\) 的计算依赖前面的 \(f\) 值和 \(g\) 的卷积。
这样的柿子考虑分治。
递归 \(solve(l,r)\) 算出 \([l,mid]\) 对 \([mid + 1, r]\) 的贡献，这个就是一个卷积取后 \(len/2\) 位的答案。于是按分治的标准做法，先递归左子区间，算完左对右的贡献后递归右子区间即可。