代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;++i)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
#define d rd()
#define pb push_back
const ll PoL=2100010;
const double pi=acos(-1.0);
struct cpl{double x,y;};
cpl operator  + (cpl a,cpl b){return (cpl){a.x+b.x,a.y+b.y};}
cpl operator  - (cpl a,cpl b){return (cpl){a.x-b.x,a.y-b.y};}
cpl operator  * (cpl a,cpl b){return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
ll but[PoL],pw[30];
struct Poly{int len;ll f[PoL];};
void out(Poly &a){f(i,0,a.len)printf("%lld ",a.f[i]);}
const ll mod=998244353,G=3,Gi=332748118;
ll qp(ll a,ll b){ll ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}return ans%mod;
}
namespace poly{
	void pre(){pw[0]=1;f(i,1,25)pw[i]=pw[i-1]*2;}
	void revbit(ll k){f(i,0,k-1)but[i]=but[i>>1]>>1|((i&1)?(k>>1):0);}
	void FFT(Poly &tag,Poly &x,Poly &y){
		static cpl a[PoL<<1];
		ll p=log2(x.len+y.len)+1;ll k=(1ll<<p);revbit(k);
		f(i,0,x.len)a[i].x=x.f[i];f(i,0,y.len)a[i].y=y.f[i];
		f(i,0,k-1)if(i<but[i])swap(a[i],a[but[i]]);
		f(dep,1,p){
			ll len=pw[dep],L=(len>>1);
			cpl Wn={cos(2.0*pi/len),sin(2.0*pi/len)},W;
			for(int j=0;j<=k-1;j+=len){W={1,0};
				for(int i=j;i<j+len/2;i++,W=W*Wn){
					cpl pa=a[i],qa=W*a[i+L];
					a[i]=pa+qa;a[i+L]=pa-qa;
				}
			}
		}f(i,0,k-1)a[i]=a[i]*a[i];f(i,0,k-1)if(i<but[i])swap(a[i],a[but[i]]);
		f(dep,1,p){
			ll len=pw[dep],L=(len>>1);
			cpl Wn={cos(2.0*pi/len),-sin(2.0*pi/len)},W;
			for(int j=0;j<=k;j+=len){W={1,0};
				for(int i=j;i<j+len/2;i++,W=W*Wn){
					cpl pa=a[i],qa=W*a[i+L];
					a[i]=pa+qa;a[i+L]=pa-qa;
				}
			}
		}tag.len=x.len+y.len;f(i,0,tag.len)tag.f[i]=(ll)((a[i].y/k/2)+0.5);
	}
	void NTT(Poly &tag,Poly &x,Poly &y){
		static ll a[PoL],b[PoL];
		ll p=log2(x.len+y.len)+1;ll k=(1ll<<p),inv=qp(k,mod-2);revbit(k);
		f(i,0,x.len)a[i]=x.f[i];f(i,0,y.len)b[i]=y.f[i];
		f(i,0,k-1)if(i<but[i])swap(a[i],a[but[i]]),swap(b[i],b[but[i]]);
		f(dep,1,p){
			ll len=pw[dep],W,Wn=qp(G,(mod-1)/len),L=(len>>1);
			for(int j=0;j<=k-1;j+=len){W=1;
				for(int i=j;i<j+L;i++,W=W*Wn%mod){
					int tt=W*a[i+L]%mod;
					a[i+L]=a[i]-tt;a[i]+=tt;
					if(a[i]>=mod)a[i]-=mod;
					if(a[i+L]<0)a[i+L]+=mod;
					tt=W*b[i+L]%mod;
					b[i+L]=b[i]-tt;b[i]+=tt;
					if(b[i]>=mod)b[i]-=mod;
					if(b[i+L]<0)b[i+L]+=mod;
				}
			}
		}f(i,0,k-1)a[i]=a[i]*b[i]%mod;f(i,0,k-1)if(i<but[i])swap(a[i],a[but[i]]);
		f(dep,1,p){
			ll len=pw[dep],W,Wn=qp(Gi,(mod-1)/len),L=(len>>1);
			for(int j=0;j<=k-1;j+=len){W=1;
				for(int i=j;i<j+len/2;i++,W=W*Wn%mod){
					int tt=W*a[i+L]%mod;
					a[i+L]=a[i]-tt;a[i]+=tt;
					if(a[i]>=mod)a[i]-=mod;
					if(a[i+L]<0)a[i+L]+=mod;
				}
			}
		}tag.len=x.len+y.len;f(i,0,tag.len)tag.f[i]=a[i]*inv%mod;
	}
}
Poly a,b,c;
int main(){
	poly::pre();a.len=d,b.len=d;
	f(i,0,a.len)a.f[i]=d;f(i,0,b.len)b.f[i]=d;
	poly::NTT(c,a,b);out(c);
	return 0;
}

评测结果