代码

#include<bits/stdc++.h>
using namespace std;
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=1ll*ans*a%mod;
		a=1ll*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);
		for(int j=0; j<n; j+=2*len)
		{
			#pragma GCC unroll(8)
			for(int k=j; k<j+len; ++k)
			{
				int tmp=1ll*a[k+len]*ppow[i][k-j]%mod;
				a[k+len]=add(a[k],mod-tmp),a[k]=add(a[k],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]=1ll*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)
{
	memcpy(a,aa,(n+1)*4),memcpy(b,bb,(m+1)*4);
	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];
}

评测结果