代码

#pragma GCC optimize("Ofast","-funroll-loops")
//#pragma GCC target("sse4.1","sse4.2","ssse3","sse3","sse2","sse","avx2","avx","popcnt","tune=native")
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const unsigned MOD=998244353,G=3;
unsigned qpow(unsigned a,unsigned b,unsigned ans=1){
	for(unsigned base=a%MOD;b>0;b/=2){
		if(b&1)ans=(ull)ans*base%MOD;
		base=(ull)base*base%MOD;
	}
	return ans;
}
inline unsigned inv(unsigned T){return qpow(T,MOD-2);}
inline unsigned add(unsigned a,unsigned b){return a+b>=MOD?(a+b-MOD):a+b;}
void D(unsigned *a,unsigned len,int op=1){
	for(unsigned i=1,k,j=len>>1;i+1<len;++i){
		if(i<j)swap(a[i],a[j]);
		k=len>>1;
		while(j>=k)j=j-k,k=k>>1;
		j+=k;
	}
	for(unsigned L=1;L<len;L*=2){
        unsigned step=qpow(G,(MOD-1)/2/L);
        if(op!=1) step=inv(step);
        for(unsigned i=0;i<len;i+=L*2){
            ull cur=1;for(unsigned k=i;k<i+L;++k){
                unsigned g=a[k],h=a[k+L]*cur%MOD;
                a[k]=add(g,h);
				a[k+L]=add(g,MOD-h);
                cur=cur*step%MOD;
            }
        }
    }
    if(op!=1)for(unsigned i=0,invN=inv(len);i<len;++i)a[i]=1ull*a[i]*invN%MOD;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	int len=1,mt=max(n,m)*2;
	while(len<mt)len*=2;
	D(a,len),D(b,len);
	for(int i=0;i<len;++i)c[i]=1ll*a[i]*b[i]%MOD;
	D(c,len,-1);
}

评测结果