题目传送门：portal
计算两个多项式mod998244353意义下的乘积。 和fft基本一样，就是把单位复数根wn换成了单位原根。 原根的定义：设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。
（a模m的阶ord m(a)就是满足at≡1modm的最小正整数t）
我们常用的模数是998244353,它的原根G=3.以下的讨论均在%P的意义下讨论。 设g=GP−1n，就是单元原根。我们显然有gn=1,gn/2=−1，类似单位复数根，于是我们只需把所有的wn换成g即可。
也就是我们有：
DFT:A(gk)=∑j=0n−1aj∗gkj
IDFT:aj=1n∑k=0n−1A(gk)∗g−kj #include #include #include #include using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 500010 #define mod 998244353 #define G 3 inline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } inline int ksm(int x,int k){ int res=1; for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) res=(ll)res*x%mod;return res; } int n,m,a[N<<2],b[N<<2],L=0,R[N<<2],inv; inline void ntt(int *a,int f){ for(int i=0;iif(ifor(int i=1;i1){ int wn=ksm(G,f==1?(mod-1)/(i*2):mod-1-(mod-1)/(i*2)); for(int j=0,p=i<<1;jint w=1; for(int k=0;kint x=a[j+k],y=(ll)a[j+k+i]*w%mod; a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod; } } }if(f==-1) for(int i=0;iint main(){ // freopen("a.in","r",stdin); n=read();m=read(); for(int i=0;i<=n;++i) a[i]=read(); for(int i=0;i<=m;++i) b[i]=read(); m=n+m;for(n=1;n<=m;n<<=1) ++L;inv=ksm(n,mod-2); for(int i=0;i>1]>>1)|(i&1)<1; ntt(a,1);ntt(b,1); for(int i=0;i1); for(int i=0;i<=m;++i) printf("%d ",a[i]); return 0; }