代码

#include<bits/stdc++.h>
using namespace std;
#define int unsigned
#define ull unsigned long long
const int mod=998244353,g=3;
const ull miu=(ull)-1/mod;
inline int add(int a,int b) { return a+b<mod?a+b:a+b-mod; }
inline int get_mod(long long a)
{
//	int r=(__int128)a*miu>>64;
	a-=((__int128)a*miu>>64)*mod;
	return a<mod?a:a-mod;
}
int qpow(int a,int b)
{
	int ans=1;
	while(b!=0)
	{
		if(b%2==1) ans=get_mod(1ll*ans*a);
		a=get_mod(1ll*a*a),b/=2;
	}
	return ans;
}
int id[(1<<21)+10];
vector<int> 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)
		{
			for(int k=j; k<j+len; ++k)
			{
				int tmp=get_mod(1ll*a[k+len]*ppow[i][k-j]);
				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]=get_mod(1ll*a[i]*inv);
}
void poly_multiply(unsigned *a,signed n,unsigned *b,signed m,unsigned *c)
{
	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;
		for(int j=0; j<len; ++j) ppow[i].push_back(noww),noww=get_mod(1ll*noww*w);
	}
	ntt(n,a),ntt(n,b);
	for(int i=0; i<n; ++i) a[i]=get_mod(1ll*a[i]*b[i]);
	intt(n,a);
	for(int i=0; i<=lst; ++i) c[i]=a[i];
}

评测结果