给定一个n次多项式F(x)，和一个m次多项式G(x)。
请求出F(x)和G(x)的卷积。
输入格式：
第一行2个正整数n,m。
接下来一行n+1个数字，从低到高表示F(x)的系数。
接下来一行m+1个数字，从低到高表示G(x))的系数。
输出格式：
一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。
保证输入中的系数大于等于 0 且小于等于9。
对于100%的数据： $n, m \leq {10}^6$ , 共计20个数据点，2s。
数据有一定梯度。
空间限制：256MB
分析：
没错，这是一道FFT模板，于是我们愉快地用NTT把它A了。
平常用的较多的都是FFT，但是FFT使用的是复数，需要开double类型，常数会比较大。但有时候我们需要求的都是整形，那么用NTT（快速数论变换）就可以把常数降低很多。具体实现理论和FFT基本无异，不过我们要把单位根换成原根，因为原根也满足单位根的性质，最后就可得到一个结论：$w_n \equiv g^{\frac {p-1} {n}} \pmod p$。具体的理论推荐这位大佬的博客。（吐槽一句，为什么开了O2之后不管是FFT还是NTT都反而更慢了？？？难道是我的代码写得太优秀？？？）
Code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e6+7; const int mod=998244353; int n,m,lim,r[N]; int G=3,Gi=332748118; ll a[N],b[N]; inline ll read() { char ch=getchar();ll num=0;bool flag=false; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){num=num*10+ch-‘0‘;ch=getchar();} return flag?-num:num; } inline void Swap(ll &x,ll &y) { x^=y,y^=x,x^=y; } inline ll power(ll x,ll y) { ll ret=1; while(y){ if(y&1)ret=(ret*x)%mod; y>>=1;x=(x*x)%mod;} return ret; } inline void ntt(ll *A,int type) { for(int i=0;i<lim;i++) if(i<r[i])Swap(A[i],A[r[i]]); for(int mid=1;mid<lim;mid<<=1){ ll wn=power((type==1)?G:Gi,(mod-1)/(mid<<1)); for(int j=0;j<lim;j+=(mid<<1)){ ll w=1; for(int k=0;k<mid;w=(w*wn)%mod,k++){ ll x=A[j+k],y=A[mid+j+k]*w%mod; A[j+k]=(x+y)%mod; A[mid+j+k]=(x-y+mod)%mod; } } } } int main() { n=read();m=read(); for(int i=0;i<=n;i++)a[i]=(read()+mod)%mod; for(int i=0;i<=m;i++)b[i]=(read()+mod)%mod; m+=n;n=0; for(lim=1;lim<=m;lim<<=1)n++; for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(n-1)); ntt(a,1);ntt(b,1); for(int i=0;i<lim;i++)a[i]=(a[i]*b[i])%mod; ntt(a,-1);ll inv=power(lim,mod-2); for(int i=0;i<=m;i++) printf("%lld ",(a[i]*inv)%mod); return 0; }
原文：https://www.cnblogs.com/cytus/p/9351623.html