代码

#include<cstdio>
#include<cctype>
#define IMP(n,act) for(int lim=(n),i=0;i^lim;++i)act
const int M=5e6+5,mod=998244353;
int buf[M<<1],*w[25];
int f[M],g[M];
inline void swap(int&a,int&b){
	int c=a;a=b;b=c;
}
inline int Getlen(const int&n){
	int len(0);while((1<<len)<n)++len;return len;
}
inline int Add(const int&a,const int&b){
	return a+b>=mod?a+b-mod:a+b;
}
inline int Del(const int&a,const int&b){
	return b>a?a-b+mod:a-b;
}
inline int pow(int a,int b=mod-2){
	int ans(1);for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;
}
inline void init(const int&n){
	const int&m=Getlen(n);int*W=buf;w[m]=W;W+=1<<m;w[m][0]=1;w[m][1]=pow(3,mod-1>>m+1);
	for(int i=2;i^(1<<m);++i)w[m][i]=1ll*w[m][i-1]*w[m][1]%mod;
	for(int k=m-1;k>=0&&(w[k]=W,W+=1<<k);--k)IMP(1<<k,w[k][i]=w[k+1][i<<1]);
}
inline void DFT(int*f,const int&M){
	const int&n=1<<M;
	for(int d=M-1,len=n>>1;d>=0;--d,len>>=1){
		for(int k=0;k^n;k+=len<<1){
			int*fl=f+(k),*fr=f+(k|len),*W=w[d],x,y;
			IMP(len,(x=*fl,y=*fr)),*fl++=Add(x,y),*fr++=1ll**W++*Del(x,y)%mod;
		}
	}
}
inline void IDFT(int*f,const int&M){
	const int&n=1<<M;
	for(int d=0,len=1;d<M;++d,len<<=1){
		for(int k=0;k^n;k+=len<<1){
			int*fl=f+(k),*fr=f+(k|len),*W=w[d],x,y;
			IMP(len,(x=*fl,y=1ll**W++**fr%mod)),*fl++=Add(x,y),*fr++=Del(x,y);
		}
	}
	const int&k=pow(n);IMP(n,f[i]=1ll*f[i]*k%mod);for(int i=1;(i<<1)<n;++i)swap(f[i],f[n-i]);
}
inline int read(){
	int n(0);char s;while(!isdigit(s=getchar()));while(n=n*10+(s^48),isdigit(s=getchar()));return n;
}
inline void write(int n){
	static char s[20];int top(0);while(s[++top]=n%10^48,n/=10);while(putchar(s[top]),--top);
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	++n;++m;IMP(n,f[i]=a[i]);IMP(m,g[i]=b[i]);init(n+m-1);
	const int&len=Getlen(n+m-1);DFT(f,len);DFT(g,len);IMP(1<<len,f[i]=1ll*f[i]*g[i]%mod);IDFT(f,len);
	IMP(n+m-1,c[i]=f[i]);
}

评测结果