代码

#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>
//#undef _GLIBCXX_HAVE_ICONV
//#include<bits/extc++.h>
//#include<ext/rope>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
const int MOD=998244353,G=3;
int qpow(int a,int b,int ans=1){
	for(int base=a%MOD;b>0;b/=2){
		if(b&1)ans=(ll)ans*base%MOD;
		base=(ll)base*base%MOD;
	}
	return ans;
}
int inv(int T){return qpow(T,MOD-2);}
int add(int x,int y){x+=y-MOD;x+=x>>31&MOD; return x;}
void D(int *a,int len,int op=1){
	for(int i=1,k,j=len>>1;i<len-1;++i){
		if(i<j)swap(a[i],a[j]);
		k=len>>1;
		while(j>=k)j=j-k,k=k>>1;
		j+=k;
	}
	for(int L=1;L<len;L*=2){
        int step=qpow(G,(MOD-1)/2/L);
        if(op!=1) step=inv(step);
        for(int i=0;i<len;i+=L*2){
            ll cur=1;for(int k=i;k<i+L;++k){
                int 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(int i=0,invN=inv(len);i<len;++i)a[i]=1ll*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;
	vector<int>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]=1ll*av[i]*bv[i]%MOD;
	D(av.data(),len,-1);
	for(int i=0;i<=n+m;++i)c[i]=av[i];
}

评测结果