NTT

detect · 2020-07-24 12:53:47 · 个人记录

一般在运用复数求解FFT的过程中难免不用到三角函数和实数，但是大多数多项式题目要对答案取模。此时fft将不再适用。

现在思考一个问题：我们能不能找到一个东西替代掉复数。

我们回顾一遍fft过程，中心运算有如下：

1. (W_n^1)^k=W_n^k
2. W_n^i=W_{n}^{i\%n}
3. W_{2n}^{2i}=W_n^i
4. W_n^{i+n/2}=-W_n^i
5. \sum_{i=0}^{i<n}W_n^i=0

现在有如下构造：

1. 在模mod=k2^n-1下运算，其中mod为质数（一般可以是998244353）

2. 设G为原根（理论上随便取一个数，一般是3）

然后把这几个定义带回上述式子，会发现都没有问题，并且现在的每一步都可以取模，于是就可以替换掉fft了。

（p.s 关于每一步的证明，啥时候想写了再来补。）

更可幸的是NTT的常数比FFT小（所以FFT各个方面都比不过NTT？）

code （微带封装版）

#include<bits/stdc++.h>
using namespace std;
#define int long long

inline int getint(){
    int ssum=0,ff=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-') ff=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) ssum=ssum*10+ch-'0';
    return ssum*ff;
}

const int M=5e6+5,G=3,mod=998244353;

inline int ksm(int x,int mi){
    int res=1;
    while(mi){
        if(mi&1) res=res*x%mod;
        x=x*x%mod;mi>>=1;
    }
    return res;
}

int n,m,lim=1,f[M],g[M],tr[M];

void Getlim(){
    while(lim<=n+m) lim<<=1;
    for(int i=0;i<=n;i++) f[i]=getint();
    for(int i=0;i<=m;i++) g[i]=getint();
    for(int i=0;i<=lim;i++) tr[i]=((tr[i>>1]>>1)|((i&1)?lim/2:0));
}

void Ntt(int *f,int fl){
    for(int i=0;i<lim;i++) if(tr[i]>i) swap(f[i],f[tr[i]]);

    for(int p=2;p<=lim;p<<=1){

        int mi=ksm(G,(mod-1)/p);
        if(fl==-1) mi=ksm(mi,mod-2);

        for(int i=0;i<lim;i+=p){
            int ori=ksm(mi,i);

            for(int j=i;j<i+(p>>1);j++){
                int tt=ori*f[j+(p>>1)];
                f[j+(p>>1)]=(f[j]-tt)%mod;
                f[j]=(f[j]+tt)%mod;
                ori=ori*mi%mod;
            }

        }

    }
}

inline void Px(int *f,int *p){
    for(int i=0;i<lim;i++) f[i]=f[i]*g[i]%mod;
}

signed main(){

    cin>>n>>m;

    Getlim();

    Ntt(f,1);Ntt(g,1);
    Px(f,g);Ntt(f,-1);

    int inv=ksm(lim,mod-2);
    for(int i=0;i<=n+m;i++) cout<<(f[i]*inv%mod+mod)%mod<<' ';

    return 0;
}