前置知识
多项式的表示：一般来说，多项式的表示方法有点表示和系数表示两种。
系数表示法：一个\(n\)次多项式可以由\(n+1\)个系数唯一确定，也即\(f(x)=\sum_{i=0}^{n}a_ix^{i}\)。
点表示法：一个\(n\)次多项式可以由\(n+1\)个各不相同的点唯一确定，设这\(n+1\)个点的坐标为\((x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n))\)，代入表达式可得方程组： \[ \begin{cases} a_0+a_1x_0+\cdots+a_nx_0^{n}=f(x_0)\\ a_0+a_1x_1+\cdots+a_nx_1^{n}=f(x_1)\\ \cdots\\ a_0+a_1x_n+\cdots+a_nx_n^{n}=f(x_n)\end{cases}\] 其系数行列式的值由范德蒙行列式可求得： \[\begin{vmatrix}1 & x_0 & \dots &x_0^{n}\\ 1 & x_1 & \dots & x_1^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & \dots & x_n^{n} \end{vmatrix} = \prod_{0\leq i\leq j \leq n}(x_i-x_j)\neq 0\] 可知多项式的系数被唯一确定。
复数的表示与运算：一个复数可以表示为\(z=a+bi(a,b\in \mathbb{R})\)，对应复平面上一点\(P(a,b)\)。其模长\(|z|=\sqrt {a^{2}+b^{2}}\),当\(z\neq0\)时，定义向量\(\overrightarrow{OP}\)与\(x\)轴正向夹角为辐角\(\theta\)，则复数也可表示为\(z=|z|(\cos\theta+i\sin\theta)\)。
复数的加（减）法：设\(z_1=a_1+ib_1\)，\(z_2=a_2+ib_2\)，则\(z_1\pm z_2=(a_1\pm a_2)+i(b_1 \pm b_2)\)。
复数的乘法：设\(z_1=a_1+ib_1\)，\(z_2=a_2+ib_2\)，则\(z_1z_2=(a_1a_2-b_1b_2)+i(a_1b_2+a_2b_1)\)。复数的乘法也可以理解为模长相乘，辐角相加。
单位根：考虑\(x^{n}=1\)在复数域上的\(n\)个解，在单位圆上将圆从\((1,0)\)开始等分成n份，这\(n\)个点均满足上述方程，将它们对应的复数记为\(\omega_n^{i}(1 \leq i \leq n-1)\)，且有\(\omega_n^{i}=\cos{\frac{2\pi i}{n}}+i\sin{\frac{2\pi i}{n}}\)。
单位根的性质：1）\(\omega_{2n}^{2k}=\omega_n^{k}\)；
2）\(\omega_n^{k+\frac{n}{2}}=-\omega_n^{k}\)；
3）\(\omega_n^{0}=\omega_n^{n}=1\)；
FFT（快速傅里叶变换）
FFT是用来解决两个多项式相乘的一种算法，FFT大致思路如下：先将两个多项式写成点表示法，则所求多项式的点值等于两个多项式点值的乘积，再将其重新转化为系数表示法。
将系数表示法转化为点表示法
取\(n\)为2的次幂，设\(A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\)，将下标按奇偶性分开，则
\(A(x)=(a_0+a_2x^{2}+\cdots+a_{n-2}x^{n-2})+(a_1x+a_3x^{3}+\dots+a_{n-1}x^{n-1})\)
\(=(a_0+a_2x^{2}+\cdots+a_{n-2}x^{n-2})+x(a_1+a_3x^{2}+\cdots+a_{n-1}x^{n-2})\)
令\(A_1(x)=a_0+a_2x+\cdots+a_{n-2}x^{\frac{n}{2}-1}\)，\(A_2(x)=a_1+a_3x+\cdots+a_{n-1}x^{\frac{n}{2}-1}\)
则\(A(x)=A_1(x^{2})+xA_2(x^{2})\)，将\(\omega_n^{k}(k<\frac{n}{2})\)代入得：
\(A(\omega_n^{k})=A_1(\omega_n^{2k})+xA_2(\omega_n^{2k})=A_1(\omega_\frac{n}{2}^{k})+\omega_n^{k}A_2(\omega_\frac{n}{2}^{k})\)
\(A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k+n})+xA_2(\omega_n^{2k+n})=A_1(\omega_\frac{n}{2}^{k})-\omega_n^{k}A_2(\omega_\frac{n}{2}^{k})\)
可以发现两部分只有后半部分的符号不一样，则若已知\(A_1(\omega_\frac{n}{2}^{k})\)与\(A_2(\omega_\frac{n}{2}^{k})\)可以求得\(A(\omega_n^{k})\)和\(A(\omega_n^{k+\frac{n}{2}})\)，从而我们可以使用递归分治的方式求得\(A(\omega_n^{k})(0\leq k\leq n-1)\)，时间复杂度\(O(nlogn)\)。
将点表示法重新转化为系数表示法
已知\(n+1\)个点的坐标\((x_0,A(x_0)),(x_1,A(x_1)),\cdots,(x_{n-1},A(x_{n-1}))\)，其中\(x_i=\omega_n^{i}(0\leq i\leq n-1)\)，先证明：\[ a_k=\frac{1}{n}\sum_{i=0}^{n-1}A(\omega_n^{i})(\omega_n^{-k})^i\]证明：
\[\sum_{i=0}^{n-1}A(\omega_n^{i})(\omega_n^{-k})^i\] \[=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^i)^j)(\omega_n^{-k})^i\] \[=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^{j-k})^i)\] \[=\sum_{j=0}^{n-1}a_j(\sum_{i=0}^{n-1}(\omega_n^{j-k})^i)\tag{1}\]
记\(S(x)=1+x+x^2+\cdots+x^{n-1}\)，考虑\(S(\omega_n^{k})\)：
1）若\(k=0\)，\(S(\omega_n^{k})=n\)；
2）若\(k\neq 0\)，\(S(\omega_n^{k})=\omega_n^0+\omega_n^k+\cdots+\omega_n^{(n-1)k}\)，\(\omega_n^{k}S(\omega_n^{k})=\omega_n^k+\omega_n^{2k}+\cdots+\omega_n^{nk}\)，两式相减可得：\((1-\omega_n^k)S(\omega_n^k)=0\)，则\(S(\omega_n^{k})=0\)。
从而\((1)=na_k\)，问题得证。
令\(B(x)=\sum_{i=0}^{n-1}A(\omega_n^{i})x^i\)，则\(a_k=\frac{1}{n}B(\omega_n^{-k})\)，问题又转化为了从系数表示法转化为点表示法。
迭代优化
注意到最终的位置为其初始位置二进制翻转后得到的，则可以将最终的位置处理出来后，向上迭代处理就可以得到最初的序列。
代码
1 |
|