代码

#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;
}
template<typename T>T inv(T a,T b){
  return qpow(a,b-2,b);
}
void init(int n,int g){
  for(int i=n>>1,w=qpow(g,(mod-1)/n,mod);i>=1;i>>=1,w=1ll*w*w%mod)for(int j=0;j<1<<(i-1);j++)wn[i+j]=j?1ll*wn[i+j-1]*w%mod:1;
}
void DIF(int n,int f[]){
  for(int i=n,d=__lg(n);i>=2;i>>=1,d--)for(int j=0;j<n;j+=i)for(int k=j,p=0,x,y;p<i>>1;k++,p++)x=f[k],y=f[k+i/2],f[k]=(x+y)%mod,f[k+i/2]=1ll*wn[(i>>1)+p]*(x-y+mod)%mod;
}
void DIT(int n,int f[]){
  for(int i=2,d=1;i<=n;i<<=1,d++)for(int j=0;j<n;j+=i)for(int k=j,p=0,x,y;p<i>>1;k++,p++)x=f[k],y=1ll*wn[(i>>1)+p]*f[k+i/2]%mod,f[k]=(x+y)%mod,f[k+i/2]=(x-y+mod)%mod;
  reverse(f+1,f+n);
  for(int i=0,invn=inv(n,mod);i<n;i++)f[i]=1ll*f[i]*invn%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];
}

评测结果