代码

#pragma GCC optimize("Ofast","-funroll-loops")
#include<bits/stdc++.h>
using namespace std;
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,uint 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 p=qpow(G,(MOD-1)/2/L);
        if(!op) p=qpow(p,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*=p)%=MOD;
            }
        }
    }
}
void poly_multiply(uint *a, const int n, uint *b,const int m, uint *c)
{
	uint len=1ull<<(__lg(max(n,m)*2)+1);
	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(uint 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;
}

评测结果