代码

#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;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;}
inline void D(unsigned *a,unsigned len,int op=1){
	for(unsigned i=1,k,j=len>>1;i+1<len;++i){
		if(i<j)a[i]^=a[j],a[j]^=a[i],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*=step)%=MOD;
            }
        }
    }
}
unsigned av[3000000];
unsigned bv[3000000];
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;
	memcpy(av,a,sizeof(unsigned)*(n+1));
	memcpy(bv,b,sizeof(unsigned)*(m+1));
	D(av,len),D(bv,len);
	for(int i=0;i<len;++i)av[i]=1ull*av[i]*bv[i]%MOD;
	D(av,len,0);
    for(unsigned i=0,invN=inv(len);i<=(unsigned)n+m;++i)c[i]=1ull*av[i]*invN%MOD;
}

评测结果