數學黑科技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;
}