class="markdown_views prism-atom-one-light"> 解决模数M不是NTT模数的情况。

多模数NTT

一般取三个模数p1p2p3做NTT，要求满足p1p2p3>nM2" role="presentation">p1p2p3>nM2$p1p2p3>n{M}^2$，即CRT模数比结果序列值要大。
然后用中国剩余定理(CRT)合并出值。
但是由于三个模数乘起来爆long long了，我们需要一些特殊trick。 首先将两个模数合并，方程变为两条
x≡a1modp1" role="presentation">x≡a1modp1$$x\equiv a1\mathrm{mod}p1$$
x≡a2modp2" role="presentation">x≡a2modp2$$x\equiv a2\mathrm{mod}p2$$
也即x=a1+kp1=a2+zp2" role="presentation">x=a1+kp1=a2+zp2$$x=a1+kp1=a2+zp2$$
两边同时模上p2" role="presentation">p2$p2$，求p1的逆元后可以计算出k在模p2意义下的值。 又因为我们所求是(a1+kp1)modp1p2" role="presentation">(a1+kp1)modp1p2$$(a1+kp1)\mathrm{mod}p1p2$$
也就是(a1+(kp1modp1p2))modp1p2" role="presentation">(a1+(kp1modp1p2))modp1p2$$(a1+(kp1\mathrm{mod}p1p2))\mathrm{mod}p1p2$$
右边括号部分展开一下，不难发现为(这是常识然而我并不会)p1(kmodp2)" role="presentation">p1(kmodp2)$$p1(k\mathrm{mod}p2)$$
又因为值域小于p1p2，这就是原始值。
从而可以计算出x。求出k后所有操作都应在modM" role="presentation">modM$\mathrm{mod}M$意义下进行。 共9" role="presentation">9$9$次NTT。。。心态是不是有点崩。 据说立大爷的做法是将三模数换成一大一小模数再用O(1)黑科技乘，这样可以做到6次。

mtt

毛爷爷用拆系数fft的方式来代替ntt.
我们考虑直接将两个多项式用fft卷积，发现值域是1023" role="presentation">1023${10}^{23}$，超出double精度范围了。 因此设一个阈值K(通常为215" role="presentation">215$2^{15}$)
将两个多项式每一项的系数拆分为aK+b" role="presentation">aK+b$aK+b$做fft.
(KA+B)(KC+D)" role="presentation">(KA+B)(KC+D)$$(KA+B)(KC+D)$$
化简后K2AC+K(BC+AD)+BD" role="presentation">K2AC+K(BC+AD)+BD$$K^{2}AC+K(BC+AD)+BD$$
将AC做卷积后，对应系数为乘上K2" role="presentation">K2$K^2$ （这个时候浮点数转为整数）加到答案中去。
其他类推。 将BC+AD放到一个多项式里idft，数一下是7次dft。 然而，因为ACidft回去后的虚部是空的，可以将BD⋅i" role="presentation">BD⋅i$BD\cdot i$加到AC中，这样一起idft回去，虚部就是BD。少一次dft。 当阈值为215" role="presentation">215$2^{15}$，长度为1e5" role="presentation">1e5$1e5$时，可以发现值域是1e14" role="presentation">1e14$1e14$的，符合double精度范围。
注意单位根不能递推求，否则精度误差呈指数级上升。
虽然理论上精度没毛病，但实际上依旧会有较大误差，需要加上一个0.5来进行四舍五入。
（好不靠谱的感觉）

推式子将两次DFT缩成一次

假如我当前要求A,B的dft，那么将B放到A的虚部中，称作Q 做一次DFT。
对于A或B的位置i，设其值为x，那么根据dft的意义，对DFT后第w位的贡献是x⋅(gnw)i" role="presentation">x⋅(gwn)i$$x\cdot (g_n^w{)}^i$$
g是复数根。对于位置w，就相当于我们要求∑x  (cos⁡θ+I⋅sin⁡θ)" role="presentation">∑x  (cosθ+I⋅sinθ)$$\sum x(\cos \theta +I\cdot \sin \theta )$$
（theta是那个单位根的i次方对应的角度。）
看看Q[i]DFT后对A’[w]和B’[w]的贡献是什么。
(Ai+I⋅Bi)⋅(gnw)i" role="presentation">(Ai+I⋅Bi)⋅(gwn)i$$(Ai+I\cdot Bi)\cdot (g_n^w{)}^i$$
=(Ai+I⋅Bi)⋅(cos⁡θ+I⋅sin⁡θ)" role="presentation">=(Ai+I⋅Bi)⋅(cosθ+I⋅sinθ)$$=(Ai+I\cdot Bi)\cdot (\cos \theta +I\cdot \sin \theta )$$
发现我们可以同时知道Ai⋅cos−Bi⋅sin与Bi⋅cos+A⋅sin" role="presentation">