代码

#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 all[(1<<21)+10],*ppow[22];
void DIF(int n,int *a)
{
	int lg=__lg(n);
	for(int i=lg-1; i>=0; --i)
	{
		int len=(1<<i);
		for(int j=0; j<n; j+=2*len)
		{
			#pragma GCC unroll(16)
			for(int k=j; k<j+len; ++k)
			{
				int x=a[k],y=a[k+len];
				a[k]=add(x,y),a[k+len]=1ll*add(x,mod-y)*ppow[i][k-j]%mod;
			}
		}
	}
}
void DIT(int n,int *a)
{
	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(16)
			for(int k=j; k<j+len; ++k)
			{
				int x=a[k],y=1ll*a[k+len]*ppow[i][k-j]%mod;
				a[k]=add(x,y),a[k+len]=add(x,mod-y);
			}
		}
	}
	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=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;
	}
	DIF(n,a),DIF(n,b);
	for(int i=0; i<n; ++i) a[i]=1ll*a[i]*b[i]%mod;
	DIT(n,a);
	for(int i=0; i<=lst; ++i) c[i]=a[i];
}

评测结果