Orz myy！

特殊模数

如果模数很特殊，(2k+1)|(p−1)$(2^k+1)|(p-1)$，(p−1)>$(p-1)>$DFT的长度，那么可以求出p的原根g，用g$g$代替单位复数根wn$w_n$。
不会原根？请点这里

一般模数

那就不能用原根代替单位复数根这种方法了。
只能用实数。
但是如果模数很大，比如1000000007$1000000007$，用double的话很可能爆精度。
目标：解决精度问题。
1.用中国剩余定理：
对每个模数分别做3次DFT。一般998244353 , 1004535809 ，9985661441
然后将三次的计算结果乘起来，对要求的模数取模即可。
可行条件：三个模数的乘积大于np2$n{p}^2$
优点：降低错误率。
缺点：做9次DFT，太慢了。常数巨大。 2.7遍DFT
将两个多项式拆一下：
Ai=ai∗P−−√+bi$A_i=a_i\ast \sqrt{P}+b_i$，Bi=ci∗P−−√+di$B_i=c_i\ast \sqrt{P}+d_i$
通过乘法分配律，则
Ai∗Bi=$A_i\ast B_i=$P∗(ai∗ci)$P\ast (a_i\ast c_i)$+$+$P−−√(ai∗di+bi∗ci)$\sqrt{P}(a_i\ast d_i+b_i\ast c_i)$+$+$bi∗di$b_i\ast d_i$
看得出来，做4次点值，分别求出ai∗ci,bi∗di,ai∗di,bi∗ci$a_i\ast c_i,b_i\ast d_i,a_i\ast d_i,b_i\ast c_i$
再做3次插值，分别对三种颜 {MOD}部分求插值即可。
然而还不优。

重头戏

myy的算法中(DFT+IDFT)的次数只有4次。
看看这究竟是什么奇技淫巧吧。
一个多项式的系数表示是这样的：A(x)=Σn−1i=0aixi$A(x)={\mathrm{\Sigma }}_{i=0}^{n-1}{a}_i{x}^i$
在做DFT的时候，ai$a_i$的虚部一开始都为0。很多人以为这没用。实际上并不然。
这个算法巧妙地利用了虚部的空间。
如果ai=ki+i∗bi$a_i=k_i+i\ast b_i$，又会怎么样？
考虑1次DFT搞定原来2次DFT得出的多项式A,B.

凑式子

问题来了，现在既要考虑充分利用虚部空间，又要考虑凑式子。
设C(x)=Σn−1i=0aix