数学黑科技2——NTT

引入

• 在你学NTT之前，你最好学一下FFT。
• https://blog.csdn.net/fengqiyuka/article/details/86553689
• 看完此博客（如果我太蒟写得太烂可以看其它博客）再来看NTT。
• 因为FFT与NTT的主要中心思想是一样的。

NTT

• 就当你们已经懂了FFT了。
• 本来点值与插值需要 O ( n 2 ) O(n^2) O(n2)才能解决，为什么能用 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)解决呢？就是因为代入值得特殊性，FFT所用的是n次单位复根，这种数有很多特殊而又优美的性质。而NTT用的也是这样的方法——它用的是，原根。

原根

• what？又是一个新名词？
• 百度百科！它的定义是这样的：

• 

• 然而这并没有什么作用
• 说得通俗点，其实对于NTT，原根的最大作用就是它的特点，如果 a a a是 b b b的原根（这两个数都是正整数），那么 a i m o d    b , i ∈ [ 0 , b − 1 ] a^i \mod b,i \in [0,b-1] aimodb,i∈[0,b−1]的b个值是两两不同的。
• 例如2不是7的原根，因为 2 2 m o d    7 = 2 5 m o d    7 2^2 \mod 7=2^5 \mod 7 22mod7=25mod7
• 而3是7的原根，因为 3 0 m o d    7 = 0 , 3 1 m o d    7 = 3 , 3 2 m o d    7 = 2 , 3 3 m o d    7 = 6 , 3 4 m o d    7 = 4 , 3 5 m o d    7 = 5 , 3 6 m o d    7 = 1 3^0 \mod 7=0,3^1 \mod 7=3,3^2 \mod 7=2,3^3 \mod 7=6,3^4 \mod 7=4,3^5 \mod 7=5,3^6 \mod 7=1 30mod7=0,31mod7=3,32mod7=2,33mod7=6,34mod7=4,35mod7=5,36mod7=1，这7个数两两不同。
• 原根到这里就介绍完毕了（是不是很简单呢？）

NTT

• 既然FFT是找到 n n n个数使得它们的n次方等于1，那么NTT是不是也是这样的呢？
• 答案是肯定的！
• 通过费马小定理我们可以得到，对于1个质数 p p p，如果 0 &lt; a &lt; p 0&lt;a&lt;p 0<a<p，则 a p − 1 ≡ 1 ( m o d &ThinSpace;&ThinSpace; p ) a^{p-1} \equiv 1(\mod p) ap−1≡1(modp)
• 那 a a a不就是mod p意义下的“（p-1）次单位复根”了吗？！
• 这样子的“（p-1）次单位复根”有很多个，之所以选择原根就是因为它的“两两不同性质”，可以使得点值时代入的数一定是两两不同的。
• 当然，如果你以为只要这样子就可以玩转NTT的话，你就未免太天真了！（我这种蒟蒻还没有学任意模数NTT）。如果你用的是朴素NTT的话，模数一定要选好！首先是要有原根，其次p-1分解质因数是2还要尽量的多。（因为FFT是n次单位复根的n是二的x次幂，这样才好分治）
• 998244353是一个好东西（原根为3,998244352=119*2^23）
• 这样子的话只要项数不超过2^23项就能用998244353做NTT
• 只要把 w n 1 w_n^1 wn1​换成 a p − 1 n a^{\frac{p-1}{n}} anp−1​就行了！！！！

与FFT区别

• NTT和FFT终究还是有区别的，不然为什么还要创造两种算法？
• 下面就让我说一下这两种算法的足与不足。
• 1.精确性：FFT会有复数乘法，涉及浮点数，会有精确度问题，而NTT全都是整数的运算，精确度相对较高。
• 2.常数：FFT会有复数乘法（又是因为复数），所以常数会比较大，而NTT相对较小（其实差别并不大，只相差10%~20%）。
• 3.适用性：FFT抛开前两个问题，几乎适用于所有的相关问题。而NTT相对来说有一个模数的限制，尽管可以用“奇技淫巧”来实现任意模数NTT，但答案终究要给力才行，不然如果不模数而答案又很大的话，NTT也就无从下手了（当然有一些DL可能做得出来）。
• 所以，这两种算法还要根据实际情况，选择合适的算法，来解决相应的题目！

代码（洛谷3803 模板题）

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=998244353,o=3;
ll a[2100000][2],b[2100000];
int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int mymax(int x,int y) {return x>y?x:y;}
int abs(int x) {return x>0?x:-x;}
ll mi(ll x,int t){
    ll d=1;
    while(t){
        if(t%2) d=(d*x)%mod;
        x=(x*x)%mod;t/=2;
    }
    return d;
}
ll ni(ll x) {return mi(x,mod-2);}
int g[2100000],t;
void find(int len,int bk){
    for(int i=0;i<len;i++){
        if(g[i]>i)
            {ll t=a[i][0];a[i][0]=a[g[i]][0];a[g[i]][0]=t;}
    }
    int d=1;t=0;
    while(1){
        len/=2;d*=2;
        if(!len) break;t=1-t;
        for(int i=1;i<=len;i++){
            ll one=mi(o,(mod-1)/d),temp=1;
            if(bk==-1) one=ni(one);
            for(int j=0;j<d/2;j++){
                int t2=(i-1)*d+j,t3=t2+d/2;
                a[t2][t]=(a[t2][1-t]+temp*a[t3][1-t])%mod;
                a[t3][t]=(a[t2][1-t]-temp*a[t3][1-t]%mod+mod)%mod;
                temp=(temp*one)%mod;
            }
        }
    }
}
ll c[2100000],d[2100000];
ll ans[2100000];
int main()
{
    int n,m,xx;scanf("%d%d\n",&n,&m);n++;m++;
    for(int i=0;i<n;i++) a[i][0]=read();
    for(int i=0;i<m;i++) b[i]=read();
    int len=n+m-1,d1=1,d2=0;
    while(d1<len) d1*=2,d2++;len=d1;
    for(int i=0;i<len;i++){
        int e=i,h=0;
        for(int j=1;j<=d2;j++) h=h*2+e%2,e/=2;
        g[i]=h;
    }
    find(len,1);
    for(int i=0;i<len;i++) c[i]=a[i][t],a[i][0]=b[i];
    find(len,1);
    for(int i=0;i<len;i++) d[i]=a[i][t];
    for(int i=0;i<len;i++) c[i]=(c[i]*d[i])%mod;
    for(int i=0;i<len;i++) a[i][0]=c[i];
    find(len,-1);
    ll h=ni(len);
    for(int i=0;i<len;i++) ans[i]=(a[i][t]*h)%mod;
    for(int i=0;i<n+m-1;i++) printf("%lld ",ans[i]);
    printf("\n");
    return 0;
}