NTT学习笔记

NTT为什么要存在于这个世界上?

很显然,FFT是不能取模的,而且用着double,那么它的精度就会损失很多。

所以,NTT就出现了,并且接下了这一伟大的任务,多项式乘法取模!

再计算FFT的时候,我们用了一种叫单位根的东西,就是因为它我们才要用double,所以只要找到一种类似于单位根的整数,我们就可以带取模地计算多项式乘法了。

而这种类似于单位根的东西就是原根。由原根的性质1(设原根为$g$的话,$1, g, g^2, g^3, g^4\dots\pmod{p}$由构成长度为$\varphi(p)$的循环节)可知,$$1\approx \omega_{\varphi(p)}^{0}$$$$g\approx \omega_{\varphi(p)}^{1}$$$$g^2 \approx \omega_{\varphi(p)}^{2}$$$$\dots$$

所以只要将单位根替换一下,再取个模,FFT就变成NTT了

模板

#include <iostream>
#include <cstdio>

const int MX=2100010, MOD=998244353, G=3;

int n, m, a[MX], b[MX];

int ksm(int _, int __){
    int ans=1;
    while(__){
        if(__&1) ans=1LL*ans*_%MOD;
        _=1LL*_*_%MOD;
        __>>=1;
    }
    return ans;
}

namespace NTT{
    int n, rev[MX];
    
    void ntt(int *P, int opt){
        for(int i=0; i<n; i++) if(rev[i]>i)
            std::swap(P[i], P[rev[i]]);
        for(int i=1; i<n; i<<=1){
            int W=opt==1 ? G : ksm(G, MOD-2);
            W=ksm(W, (MOD-1)/(i*2));
            for(int p=i<<1, j=0; j<n; j+=p){
                int w=1;
                for(int k=0; k<i; k++, w=1LL*w*W%MOD){
                    int X=P[j+k], Y=1LL*P[i+j+k]*w%MOD;
                    P[j+k]=(X+Y)%MOD, P[i+j+k]=((X-Y)%MOD+MOD)%MOD;
                }
            }
        }
    }
    
    void conv(int *a, int *b, int len){
        for(n=1; n<=len; n<<=1);
        for(int i=0; i<n; i++)
            rev[i]=(rev[i>>1]>>1) | ((i&1) ? n>>1 : 0);
        ntt(a, 1); ntt(b, 1);
        for(int i=0; i<n; i++) a[i]=1LL*a[i]*b[i]%MOD;
        ntt(a, -1);
        int inv=ksm(n, MOD-2);
        for(int i=0; i<n; i++) a[i]=1LL*a[i]*inv%MOD;
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0; i<=n; i++) scanf("%d", a+i);
    for(int i=0; i<=m; i++) scanf("%d", b+i);
    NTT::conv(a, b, n+m);
    for(int i=0; i<=n+m; i++) printf("%d ", a[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注