?

NTT模板

---

#include<bits/stdc++.h> using namespace std; #define LL long long const int MAXL=22; const int MAXN=1<<MAXL; const int Mod=998244353; int rev[MAXN],A[MAXN],B[MAXN],C[MAXN]; int fast_pow(int a,int b){int ans=1;while(b){if(b&1)ans=1ll*ans*a%Mod;a=1ll*a*a%Mod;b>>=1;}return ans; } void transform(int n,int *t,int typ){for(int i=0;i<n;i++)if(i<rev[i])swap(t[i],t[rev[i]]);for(int step=1;step<n;step<<=1){int gn=fast_pow(3,(Mod-1)/(step<<1));//3為998244353的原根 for(int i=0;i<n;i+=(step<<1)){int g=1;for(int j=0;j<step;j++,g=1ll*g*gn%Mod){int x=t[i+j],y=1ll*g*t[i+j+step]%Mod;t[i+j]=(x+y)%Mod;t[i+j+step]=(x-y+Mod)%Mod;}}}if(typ==1)return;for(int i=1;i<n/2;i++)swap(t[i],t[n-i]);int inv=fast_pow(n,Mod-2);for(int i=0;i<n;i++)t[i]=1ll*t[i]*inv%Mod; } void ntt(int p,int *A,int *B,int *C){transform(p,A,1);transform(p,B,1);for(int i=0;i<p;i++)C[i]=1ll*A[i]*B[i]%Mod;transform(p,C,-1); } int main(){int n,m;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 p=1,l=0;while(p<=n+m)p<<=1,l++;for(int i=0;i<p;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));ntt(p,A,B,C);for(int i=0;i<=n+m;i++)printf("%d ",C[i]);return 0; }

轉載于:https://www.cnblogs.com/dream-maker-yk/p/9676402.html

總結

以上是生活随笔為你收集整理的【模板】NTT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。