[模板]NTT

贴个模板...

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=2100005,tt=998244353;
int n,m,a[maxn],b[maxn],re[maxn];
int qsm(int w,int b){int num=1;while(b){if (b&1) num=(LL)num*w%tt;w=(LL)w*w%tt;b>>=1;}return num;}
void NTT(int a[],int f){
    for (int i=0;i<n;i++) if (i<re[i]) swap(a[i],a[re[i]]);
    for (int i=1;i<n;i<<=1){
        int wn=qsm(3,(tt-1)/(i<<1)),w=1,x,y;
        if (f<0) wn=qsm(wn,tt-2);
        for (int j=0;j<n;j+=(i<<1),w=1)
        for (int k=0;k<i;k++,w=(LL)w*wn%tt){
            x=a[j+k];y=(LL)a[j+k+i]*w%tt;
            a[j+k]=(x+y)%tt;a[j+k+i]=(x-y+tt)%tt;
        }
    }
    if (f<0) for (int i=0,INV=qsm(n,tt-2);i<n;i++) a[i]=(LL)a[i]*INV%tt;
}
int main(){
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);
    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]);
    int l=0;for (m+=n,n=1;n<=m;n<<=1,l++);
    for (int i=0;i<n;i++) re[i]=((re[i>>1]>>1)|(i&1)<<(l-1));
    NTT(a,1);NTT(b,1);for (int i=0;i<n;i++) a[i]=(LL)a[i]*b[i]%tt;NTT(a,-1);
    for (int i=0;i<=m;i++) printf("%d ",a[i]);return 0;
} 

[模板]NTT

原文：https://www.cnblogs.com/CHNJZ/p/10449066.html