代码

#include<bits/stdc++.h>
#define ll long long
#define re register
#define INF 2147483647
using namespace std;

const int p=998244353,G=3;
const int N=1350000; 
inline int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%p)
		if(b&1) ans=1ll*ans*a%p;
	return ans;	
}

inline int add(int a,int b) 
{
	return a+b>=p?a+b-p:a+b;
}

inline int sub(int a,int b)
{
	return a-b<0?a-b+p:a-b;	
} 

const int invG=ksm(G,p-2);
int rev[N<<1],rev_len,n,m;
int F1[N<<1],F2[N<<1],ans[N<<1];

inline void getrev(int n)
{
	if(rev_len==n) return;
	rev_len=n;
	for(int i=0;i<n;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
}

void NTT(int *f,bool flag,int n)
{
	getrev(n);
	for(int i=0;i<n;i++)
		if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int len=2;len<=n;len<<=1)
	{
		int w=ksm((flag?G:invG),(p-1)/len);
		for(int k=0;k<n;k+=len)
		{
			int buf=1;
			for(int i=k;i<k+(len>>1);i++,buf=1ll*buf*w%p)
			{
				int tmp=1ll*buf*f[i+(len>>1)]%p;
				f[i+(len>>1)]=sub(f[i],tmp);
				f[i]=add(f[i],tmp);
			} 
		}
	}
	if(!flag)
	{
		int invn=ksm(n,p-2);
		for(int i=0;i<n;i++) f[i]=1ll*f[i]*invn%p;
	}
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	int len=1;
	for(;len<=n+m;len<<=1);
	for(int i=0;i<=n;i++) F1[i]=a[i];
	for(int i=0;i<=m;i++) F2[i]=b[i]; 
	NTT(F1,1,len),NTT(F2,1,len);
	for(int i=0;i<len;i++) ans[i]=1ll*F1[i]*F2[i]%p;
	NTT(ans,0,len);
	for(int i=0;i<=n+m;i++) c[i]=ans[i];  
}

评测结果