代码

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<21)+20;
const int mod=998244353;
typedef vector<int> vec;
typedef unsigned long long ull;

namespace IO {
	inline char nc(){
		static char buf[500005],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,500000,stdin),p1==p2)?EOF:*p1++;
	}
	char out[500005],*pout=out,*eout=out+500000;
	inline void flush() { fwrite(out,1,pout-out,stdout),pout=out; }
	inline void pc(char c) { pout==eout&&(fwrite(out,1,500000,stdout),pout=out); (*pout++)=c; }
	template<typename T> inline void put(T x,char suf) {
		static char stk[40];int top=0; while(x) stk[top++]=x%10,x/=10;
		!top?pc('0'),0:0; while(top--) pc(stk[top]+'0'); pc(suf);
	}
	inline int read(){
		char ch=nc(); int sum=0; for(;ch<'0'||ch>'9';ch=nc());
		while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+ch-48,ch=nc();
		return sum;
	}
}
#define Rint IO::read()
using IO::put;
using IO::nc;
//IObuff没判负数 

namespace Math{
	inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
	inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
	inline void inc(int &x,int y){x=add(x,y);}
	inline void rec(int &x,int y){x=dec(x,y);}
	inline int ksm(int x,int y){
		int ret=1;
		for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
		return ret; 
	}
	int iv[N],tp;
	inline void init_inv(int n){
		if(!tp){iv[0]=iv[1]=1;tp=2;}
		for(;tp<=n;++tp) iv[tp]=1ll*(mod-mod/tp)*iv[mod%tp]%mod;
	}
}
using namespace Math;

int Wn[N<<1],lg[N],r[N],tot;
inline void init_poly(int n){
	int p=1;while(p<=n)p<<=1;
	for(int i=2;i<=p;++i) lg[i]=lg[i>>1]+1;
	for(int i=1;i<p;i<<=1){
		int wn=ksm(3,(mod-1)/(i<<1));
		Wn[++tot]=1;
		for(int j=1;j<i;++j) ++tot,Wn[tot]=1ll*Wn[tot-1]*wn%mod;
	}
}
inline void init_pos(int lim){
	int len=lg[lim]-1;
	for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len);
}

ull fr[N];
const ull Mod=998244353;
inline void NTT(int *f,int lim,int tp){
	for(int i=0;i<lim;++i) fr[i]=f[r[i]];
	for(int mid=1;mid<lim;mid<<=1){
		for(int len=mid<<1,l=0;l+len-1<lim;l+=len){
			for(int k=l;k<l+mid;++k){
				ull w1=fr[k],w2=fr[k+mid]*Wn[mid+k-l]%Mod;
				fr[k]=w1+w2;fr[k+mid]=w1+Mod-w2; 
			}
		}
	}
	for(int i=0;i<lim;++i) f[i]=fr[i]%Mod;
	if(!tp){
		reverse(f+1,f+lim);
		int iv=ksm(lim,mod-2);
		for(int i=0;i<lim;++i) f[i]=1ll*f[i]*iv%mod;
	}
}
int f[N],g[N];
void poly_multiply(unsigned *a,int n,unsigned *b,int m,unsigned *c){
	int rec=n+m-1;
	int len=lg[rec],lim=1<<len+1;
	init_pos(lim);
	for(int i=0;i<n;++i) f[i]=a[i];
	for(int i=0;i<m;++i) g[i]=b[i];
	NTT(f,lim,1);NTT(g,lim,1);
	for(int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
	NTT(f,lim,0);
	for(int i=0;i<rec;++i) c[i]=f[i];
}

评测结果