代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define cpy(f,g,n) memcpy(f,g,sizeof(ll) * n)
#define mem(f,n) memset(f,0,sizeof(ll) * n)
#define in inline
#define pb(x) push_back(x)
#define db double  
const int N = 4e6+1e5;
const ll mod = 998244353,g = 3;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int ksm(int x,int y = mod-2){
    int ans = 1;
    while(y){
        if(y & 1)ans = 1ll * ans * x % mod;
        x = 1ll * x * x % mod,y >>= 1;
    }return ans;
}

int rev[N];
ll a[N],b[N],invg = ksm(g);

void prerev(int n){
	ll b = __builtin_ctz(n);
    for(int i = 1;i <= n;i++)rev[i] = ((rev[i>>1]>>1) | (i & 1)<<(b - 1));
}
void NTT(unsigned *f,int n,int op){
	prerev(n);
    for(int i = 0;i <= n;i++)if(i < rev[i])swap(f[i],f[rev[i]]);
    for(int len = 1;len <= (n>>1);len <<= 1){
        ll tg = ksm(op ? g : invg,(mod - 1) / (len<<1));
        for(int i = 0;i + (len<<1) <= n;i += (len<<1)){
            ll gg = 1;
            for(int j = i;j < i + len;j++){
                ll x = f[j],y = gg * f[j+len] % mod;
                f[j] = (x + y) % mod,f[j+len] = (x - y + mod) % mod;
                gg = gg * tg % mod;
            }
        }
    }
    if(!op){
    	ll invn = ksm(n);
    	for(int i = 0;i <= n;i++)f[i] = f[i] * invn % mod;
	}
}
void px(unsigned *f,unsigned *g,int n){for(int i = 0;i <= n;i++)f[i] = f[i] * g[i] % mod;}
void mol(unsigned *f,unsigned *g,int n,int m,int lim){
	unsigned tmp[N] = {0};
    int t = 1;
	while(t < n + m)t <<= 1;
	mem(tmp,t),cpy(tmp,g,t);
	NTT(f,t,1),NTT(tmp,t,1);
	px(f,tmp,t),NTT(f,t,0);
	mem(tmp,t),mem(f+lim,t-lim);
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	mol(a,b,n + 1,m + 1,n + m + 2);
	for(int i = 0;i <= n + m;i++)c[i] = a[i];
}

评测结果