代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int wn[2097152],f[2097152],g[2097152],h[2097152];
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
void init(int n,int g){
  wn[0]=1,wn[n>>2]=qpow(g,(mod-1)/n,mod);
  for(int i=n>>3;i>=1;i>>=1)wn[i]=1ll*wn[i<<1]*wn[i<<1]%mod;
  for(int i=1;i<n>>1;i++)wn[i]=1ll*wn[i&(i-1)]*wn[i&-i]%mod;
}
void DIF(int n,int f[]){
  for(int i=n>>1;i>=1;i>>=1)for(int j=0,p=0;j<n;j+=i<<1,p++)for(int k=j,x,y;k<j+i;k++)x=f[k],y=1ll*wn[p]*f[k+i]%mod,f[k]=(x+y)%mod,f[k+i]=(x-y+mod)%mod;
}
void DIT(int n,int f[]){
  for(int i=1;i<=n>>1;i<<=1)for(int j=0,p=0;j<n;j+=i<<1,p++)for(int k=j,x,y;k<j+i;k++)x=f[k],y=f[k+i],f[k]=(x+y)%mod,f[k+i]=1ll*wn[p]*(x-y+mod)%mod;
  reverse(f+1,f+n);
  for(int i=0;i<n;i++)f[i]=1ll*f[i]*(mod-(mod-1)/n)%mod;
}
void poly_multiply(unsigned a[],int n,unsigned b[],int m,unsigned c[]){
  for(int i=0;i<=n;i++)f[i]=a[i];
  for(int i=0;i<=m;i++)g[i]=b[i];
  init(2<<__lg(n+m),3),DIF(2<<__lg(n+m),f),DIF(2<<__lg(n+m),g);
  for(int i=0;i<2<<__lg(n+m);i++)h[i]=1ll*f[i]*g[i]%mod;
  DIT(2<<__lg(n+m),h);
  for(int i=0;i<=n+m;i++)c[i]=h[i];
}

评测结果