代码

#include<bits/stdc++.h>
#define M_PI		3.14159265358979323846
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define de(x) cerr << #x << " = " << x << endl;
const int MAX_N=1<<21;//2097152

namespace Poly{// N=n<<1
	const int M=998244353,G=3,N=1<<21;int rev[N],wn[N];
	inline int Q(int a,int b){// 快速幂 
		for(int ba=a,ans=1;;b>>=1,ba=(ll)ba*ba%M)
		if(b&1)ans=(ll)ans*ba%M;else if(!b)return ans;
	}
	inline void I(int n,int k){// 预处理 !! [n=2^k] k>0
		wn[0]=1;ll s=Q(G,(M-1)/n);
		for(int i=1;i<=n;++i) 
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1)),wn[i]=wn[i-1]*s%M;
	}
	inline void D(int *a,int n,int op=1){
		for(int i=0;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
		for(int L=1,i,k,t;L<n;L<<=1)for(i=0;i<n;i+=L<<1)for(k=i,t=n/(L<<1);k<i+L;++k){
        	ll c=(op==1)?wn[t*(k-i)]:wn[n-t*(k-i)];int g=a[k],h=a[k+L]*c%M;
			a[k+L]=g-h<0?g-h+M:g-h;a[k]=g+h>=M?g+h-M:g+h;
        }
	}
	void T(int *a,int *b,int n,int m,unsigned *c,int len){// a[k]=\sum k=i+j a[i]*b[j]
		m=n+m,n=1;int k=0;while(n<m)n*=2,++k;//I(n,k) : 预处理 rev & wn
		I(n,k);D(a,n);D(b,n);for(int i=0;i<n;++i)a[i]=1ll*a[i]*b[i]%M;
		D(a,n,-1);	
	    for(int i=0,invN=Q(n,M-2);i<len;++i)c[i]=1ll*a[i]*invN%M;	
	}
};
int a[MAX_N],b[MAX_N];
void poly_multiply(unsigned *ax, int n, unsigned *bx, int m, unsigned *c)
{
	n++,m++;
	for(int i=0;i<n;++i){
		a[i]=ax[i];
	}
	for(int i=0;i<m;++i){
		b[i]=bx[i];
	}
	Poly::T(a,b,n,m,c,n+m);
}

评测结果