代码

#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);
		if(len<4)
		{
			for(int j=0; j<n; j+=2*len)
			{
				int *x=a+j,*y=a+j+len;
				for(int k=j; k<j+len; ++k)
				{
					int tmp=1ll*(*y)*ppow[i][k-j]%mod;
					(*y)=add(*x,mod-tmp),*x=add(*x,tmp),++x,++y;
				}
			}
		}
		else
		{
			int tmp0,tmp1,tmp2,tmp3;
			for(int j=0; j<n; j+=2*len)
			{
				int *x=a+j,*y=a+j+len;
				for(int k=j; k<j+len; k+=4)
				{
					tmp0=1ll*(*y)*ppow[i][k-j]%mod;
					(*y)=add(a[k],mod-tmp0),(*x)=add((*x),tmp0);
					tmp1=1ll*(*(y+1))*ppow[i][k+1-j]%mod;
					(*(y+1))=add(a[k+1],mod-tmp1),(*(x+1))=add((*(x+1)),tmp1);
					tmp2=1ll*(*(y+2))*ppow[i][k+2-j]%mod;
					(*(y+2))=add(a[k+2],mod-tmp2),(*(x+2))=add((*(x+2)),tmp2);
					tmp3=1ll*(*(y+3))*ppow[i][k+3-j]%mod;
					(*(y+3))=add(a[k+3],mod-tmp3),(*(x+3))=add((*(x+3)),tmp3);
					x+=4,y+=4;
				}
			}
		}
	}
}
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];
}

评测结果