orz神鱼
by yyk504 @ 2019-05-18 14:27:56
我从我的blog里面截了一段出来。。
***
这里有一只多项式qwq：
(假设$n$为奇数)
### $A(x)=a_0+a_1x+a_2x^2+...+a_nx^n$
这里还有另外两只多项式：
### $A_1(x)=a_0+a_2x+a_4x^2+...+a_{n-1}x^{\frac{n-1}{2}}$
### $A_2(x)=a_1+a_3x+a_5x^2+...+a_nx^{\frac{n-1}{2}}$
观察一下，可以发现一个神奇的事情，那就是：
### $A(x)=A_1(x^2)+xA_2(x^2)$
我们把$\omega_n^k\space (k<\frac{n}{2})$代替$x$，得到这个：
### $A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})$
根据复数单位根的性质，$\omega_n^{2k}=\omega_{n/2}^k$，这个式子就能变形为：
### 1：$A(\omega_n^k)=A_1(\omega_{n/2}^k)+\omega_n^kA_2(\omega_{n/2}^k)$
这样又有什么用？先别急，我们再把$\omega_n^{k+n/2}$带进去看看：
### $A(\omega_n^{k+n/2})=A_1(\omega_n^{2k+n})+\omega_n^{k+n/2}A_2(\omega_n^{2k+n})$
这里又要用到复数单位根的一个性质了。 $\omega_n^{k+n/2}=-\omega_n^k$
所以我们就可以类比第一个式子的方法，将其化简为：
### 2：$A(\omega_n^{k+n/2})=A_1(\omega_{n/2}^k)-\omega_n^kA_2(\omega_{n/2}^k)$
****
如果还没看出来，我们设
$$x=A_1(\omega_{n/2}^k)$$
$$y=\omega_n^kA_2(\omega_{n/2}^k)$$
那么
$$A(\omega_n^k)=x+y$$
$$A(\omega_n^{k+n/2})=x-y$$
由此就实现快速计算多项式$A$在$n$个单位根上的点值
by NaCly_Fish @ 2019-05-18 14:30:35
@[SodiumThiocyanate](/space/show?uid=113348)
by NaCly_Fish @ 2019-05-18 14:31:00
@[NaCly_Fish](/space/show?uid=115864) Orz & Thanks
by 已注销^6Gv$vkg @ 2019-05-18 14:33:01
**而A1(x)和A2(x)都是规模缩小了一半的子问题**
这是因为根据折半引理，我们发现对于n次单位复数根，在公式A[x]=A1[x^2]+xA2[x^2]中前半部分的值和后半部分的值是一样的，所以我们的问题就变成求复数根在A1[]中的值，显然我们需要递归logx次。
当x=1时，我们不再二分直接返回其值即可，故总的求A[x]的复杂度为O(logn)
怎么感觉我这解释的和没解释一样啊......是我太弱了OwO
by NekoPass @ 2019-05-18 14:37:48
orz
by 开始新的记忆 @ 2019-05-18 15:49:07
看不懂QAQ
by 三生万物 @ 2019-05-18 17:25:45