代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353,g=3;
inline int add(int a,int b) { return a+b<mod?a+b:a+b-mod; }
int qpow(int a,int b)
{
	int ans=1;
	while(b!=0)
	{
		if(b%2==1) ans=ans*a%mod;
		a=a*a%mod,b/=2;
	}
	return ans;
}
int id[(1<<21)+10];
int all[(1<<21)+10],*ppow[22];
void ntt(int n,int *a)
{
	for(int i=0; i<n; ++i)
	{
		if(id[i]<i) swap(a[i],a[id[i]]);
	}
	int lg=__lg(n);
	for(int i=0; i<lg; ++i)
	{
		int len=(1<<i);
		if(len<4)
		{
			for(int j=0; j<n; j+=2*len)
			{
				for(int k=j; k<j+len; ++k)
				{
					int tmp=a[k+len]*ppow[i][k-j]%mod;
					a[k+len]=add(a[k],mod-tmp),a[k]=add(a[k],tmp);
				}
			}
		}
		else
		{
			for(int j=0; j<n; j+=2*len)
			{
				for(int k=j; k<j+len; k+=4)
				{
					int tmp=a[k+len]*ppow[i][k-j]%mod;
					a[k+len]=add(a[k],mod-tmp),a[k]=add(a[k],tmp);
					tmp=a[k+1+len]*ppow[i][k+1-j]%mod;
					a[k+1+len]=add(a[k+1],mod-tmp),a[k+1]=add(a[k+1],tmp);
					tmp=a[k+2+len]*ppow[i][k+2-j]%mod;
					a[k+2+len]=add(a[k+2],mod-tmp),a[k+2]=add(a[k+2],tmp);
					tmp=a[k+3+len]*ppow[i][k+3-j]%mod;
					a[k+3+len]=add(a[k+3],mod-tmp),a[k+3]=add(a[k+3],tmp);
				}
			}
		}
	}
}
void intt(int n,int *a)
{
	ntt(n,a),reverse(a+1,a+n);
	int inv=qpow(n,mod-2);
	for(int i=0; i<n; ++i) a[i]=a[i]*inv%mod;
}
int a[(1<<21)+10],b[(1<<21)+10];
void poly_multiply(unsigned *aa,signed n,unsigned *bb,signed m,unsigned *c)
{
	for(int i=0; i<=n; ++i) a[i]=aa[i];
	for(int i=0; i<=m; ++i) b[i]=bb[i];
	int lst=n+m;
	n=(1<<__lg(n+m)+1);
	int lg=__lg(n);
	for(int i=1; i<=lg; ++i)
	{
		for(int j=(1<<i-1); j<(1<<i); ++j) id[j]=id[j-(1<<i-1)]+(1<<lg-i);
	}
	for(int i=0; i<lg; ++i)
	{
		int len=(1<<i),w=qpow(g,(mod-1)/len/2),noww=1;
		ppow[i]=(i==0?all:ppow[i-1]+(1<<i-1));
		for(int j=0; j<len; ++j) ppow[i][j]=noww,noww=1ll*noww*w%mod;
	}
	ntt(n,a),ntt(n,b);
	for(int i=0; i<n; ++i) a[i]=1ll*a[i]*b[i]%mod;
	intt(n,a);
	for(int i=0; i<=lst; ++i) c[i]=a[i];
}

评测结果