代码

#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;
typedef unsigned uint;

const uint MOD=998244353,G=3;
inline uint qpow(uint a,uint b,uint ans=1){for(ull s=a%MOD;b;(s*=s)%=MOD,b/=2)if(b&1)ans=ans*s%MOD;return ans;}
inline uint add(uint a,uint b){return a+b>=MOD?(a+b-MOD):a+b;}
inline void D(uint *a,uint len,int op=1){
	for(uint i=1,k,j=len>>1;i+1<len;++i,j+=k){
		if(i<j)a[i]^=a[j],a[j]^=a[i],a[i]^=a[j];
		k=len/2;
		while(j>=k)j=j-k,k=k/2;
	}
	for(uint L=1;L<len;L*=2){
        uint step=qpow(G,(MOD-1)/2/L);
        if(!op) step=qpow(step,MOD-2);
        for(uint i=0;i<len;i+=L*2){
            ull cur=1;for(uint k=i;k<i+L;++k){
                uint g=a[k],h=a[k+L]*cur%MOD;
                a[k]=add(g,h);
				a[k+L]=add(g,MOD-h);
                (cur*=step)%=MOD;
            }
        }
    }
}
void poly_multiply(uint *a, int n, uint *b, int m, uint *c)
{
	int len=1,mt=max(n,m)*2;
	while(len<mt)len*=2;
	vector<uint>av(len),bv(len);
	for(int i=0;i<=n;++i)av[i]=a[i];
	for(int i=0;i<=m;++i)bv[i]=b[i];
	D(av.data(),len),D(bv.data(),len);
	for(int i=0;i<len;++i)av[i]=1ull*av[i]*bv[i]%MOD;
	D(av.data(),len,0);
    for(uint i=0,invN=qpow(len,MOD-2);i<=(uint)n+m;++i)c[i]=1ull*av[i]*invN%MOD;
}

评测结果