NTT和它的常数技巧

第一次做FFT/NTT的题就是一题超难的…想看系数优化的可以跳2。

1. FFT/NTT简单原理：

总结来说：

1. $O(NlogN)$把多项式系数表示转换成点表示
2. $O(N)$在点操作上做各种操作
3. $O(NlogN)$把点表示转换回系数表示

假设我们现在要做大整数相乘$$(\overline{a_N...a_2{a}_1{a}_0}{)}_{10}\ast (\overline{b_N...b_2{b}_1{b}_0}{)}_{10}$$正常来说我们需要一位一位来乘，需要$O(N^2)$复杂度。

让我们看看另外一个思路：
其实我们要计算$$F_a(10)\ast F_b(10)$$
，其中 { F a ( x ) = a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x N F b ( x ) = b 0 + b 1 ∗ x + b 2 ∗ x 2 + . . . + b m ∗ x N

{Fa​(x)=a0​+a1​∗x+a2​∗x2+...+an​∗xNFb​(x)=b0​+b1​∗x+b2​∗x2+...+bm​∗xN​
令$$G(x)=F_a(x)\ast F_b(x)$$
如果我们可以求出$G(x)$，那么代入$G(10)$就可以在$O(2N)=O(N)$（多项式应该会有$2N-1$项）时间内算出结果来了！

传统暴力求$G(x)$需要$O(N^2)$时间，但是FFT/NTT可以做到在$O(NlogN)$求出来。我们上面看到的表示叫做系数表示法，其实多项式还可以用点表示：
{ F a ( x ) = [ ( x 0 , F a ( x 0 ) ) , ( x 1 , F a ( x 1 ) ) , . . . , ( x n , F a ( x N ) ) ] F b ( x ) = [ ( x 0 , F b ( x 0 ) ) , ( x 1 , F b ( x 1 ) ) , . . . , ( x n , F b ( x N ) ) ]

{Fa​(x)=[(x0​,Fa​(x0​)),(x1​,Fa​(x1​)),...,(xn​,Fa​(xN​))]Fb​(x)=[(x0​,Fb​(x0​)),(x1​,Fb​(x1​)),...,(xn​,Fb​(xN​))]​就跟两点可以确定一直线、三个点可以确定一个二次方程一样，只要有$N+1$个点，我们就可以确定一个最高次为$N$的多项式。

得到这些点后，我们可以在$O(N)$时间内得到$G(x)$的点表示（乘起来就好啦）：
G ( x ) = [ ( x 0 , G ( x 0 ) ) , ( x 0 , G ( x 0 ) ) , . . . , ( x n , G ( x N ) ) ] = [ ( x 0 , F a ( x 0 ) F b ( x 0 ) ) , ( x 1 , F a ( x 1 ) F b ( x 1 ) ) , . . . , ( x n , F a ( x N ) F b ( x N ) ) ]

G(x)​=[(x0​,G(x0​)),(x0​,G(x0​)),...,(xn​,G(xN​))]=[(x0​,Fa​(x0​)Fb​(x0​)),(x1​,Fa​(x1​)Fb​(x1​)),...,(xn​,Fa​(xN​)Fb​(xN​))]​
问题是，光是求$F_a(x)$的点表示就需要$O(N^2)$的时间！（因为总共有$N$个$x$，对于每个$x$我们要用$N$次加法来求$F_a(x)$）。

假设$n$是一个奇数（如果不够可以补零），$F_a(x)$可以变成这样子
F a ( x ) = a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x n = ( a 0 + a 2 ∗ x 2 + . . . + a n − 1 ∗ x n − 1 ) + ( a 1 ∗ x + a 3 ∗ x 3 + . . . + a n ∗ x n ) = ( a 0 + a 2 ∗ x 2 + . . . + a n − 1 ∗ x n − 1 ) + x ( a 1 + a 3 ∗ x 2 + . . . + a n ∗ x n − 1 ) = U ( x ) + x V ( x )

Fa​(x)​=a0​+a1​∗x+a2​∗x2+...+an​∗xn=(a0​+a2​∗x2+...+an−1​∗xn−1)+(a1​∗x+a3​∗x3+...+an​∗xn)=(a0​+a2​∗x2+...+an−1​∗xn−1)+x(a1​+a3​∗x2+...+an​∗xn−1)=U(x)+xV(x)​
拆解出来的奇偶项其实就有一点分制的意味了。如果我们可以找到两个特殊的输入$x_{\alpha }$、$x_{\beta }$使得
{ F a ( x α ) = U ( x ′ ) − x V ( x ′ ) F a ( x β ) = U ( x ′ ) + x V ( x ′ )

{Fa(xα)=U(x′)−xV(x′)Fa(xβ)=U(x′)+xV(x′)" role="presentation" style="position: relative;">{Fa(xα)=U(x′)−xV(x′)Fa(xβ)=U(x′)+xV(x′)$$\{\begin{array}{l}{F}_a(x_{\alpha })=U(x^{\prime })-xV(x^{\prime })\\ F_a(x_{\beta })=U(x^{\prime })+xV(x^{\prime })\end{array}$$

{Fa​(xα​)=U(x′)−xV(x′)Fa​(xβ​)=U(x′)+xV(x′)​其中$x^{\prime }$是跟$x$有关的一个量，那么我们可以只求$U(x^{\prime })$、$V(x^{\prime })$，从而同时求得$F_a(x_{\alpha })$、$F_a(x_{\beta })$。注意到$U$、$V$的规模都是之前的一半，所以最后的复杂度是$O(NlogN)$。

怎么找到特殊的$x_{\alpha }$、$x_{\beta }$和$k^{\prime }$呢？这里就涉及到各种复杂但巧妙的数学了。同时，我们还需要把点表示变回成多项式表示，这个可以用相似的步骤在$O(NlogN)$时间做到。

想读更多？

• FFT
  • https://www.cnblogs.com/RabbitHu/p/FFT.html
  • https://blog.csdn.net/enjoy_pascal/article/details/81478582
• NTT
  • https://zhuanlan.zhihu.com/p/80297169
  • https://www.cnblogs.com/zhouzhendong/p/fast-fourier-transform.html
• 怎么用FFT/NTT
  • 入门
  • 有点抽象有点进阶

2. NTT常数优化

尽管FFT/NTT是$O(NlogN)$的，但它的常数有时可以很大以至于TLE。这次学到了一些技巧：

自底向上非递归优化

把递归版本写成自底向上的非递归，常规优化了

蝴蝶优化

这个很多博客都有写，常规优化了

缓存逆

inverse的时候（求IFFT或者INTT），需要计算N的逆，这个缓存下来似乎不能省太多时间

正向NTT的根得到逆向NTT的根

NTT有一个特点就是除了第一个根，第二到最后一个根的顺序，在正向NTT和逆向NTT的时候恰好是相反的。可以只求一个。

缓存+递增根数组

观察一下$n=2^2$的根数组和$n=2^3$的根数组，后者其实是前者插入一些值得到的。我们可以维护并复用一个递增的根数组来省时间。

根数组减半

对于一个$N$长的数组，我们可以只用$N/2$个根来完成正/反向NTT。但反向的NTT要求我们从Maxsize开始取根而不是从最小开始（我也暂时想不懂里面的数学T_T）。

特判数组相同

当两个输入多项式相同的时候，第二个数组可以跳过正向的NTT

暴力处理小数组

当$n$很小(150?)的时候，$O(N^2)$的暴力不比高常数系数的$O(NlogN)$差

裁剪结果多项式

假设两个输入的多项式长度为$n$、$m$的时候，我们可以把结果裁剪到$n+m-1$长度。好处是如果有多个多项式要相乘，这样子做可以减少一些NTT时候的长度。

缓存交换数组的下标

对于每个$n$，可以把要交换的下标缓存下来，每次调用就可以了。注意如果用一个unordered_map>来缓存数组的话，一定要用一个引用来访问vector里的东西，要不然indexing看起来$O(1)$的操作其实常数也是很高的。

Show me the code

官方题解挺全面的，就是要自己慢慢读：https://www.codechef.com/submit/EXPDIF?tab=solution
（如果有人看帖子的话）想要参考我的模板的话可以留言。