代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int 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 DIF(int n,int f[]){
  for(int i=n;i>=2;i>>=1){
    int wn=qpow(3,(mod-1)/i,mod);
    for(int j=0;j<n;j+=i){
      int w=1;
      for(int u=j,v=j+i/2;u<j+i/2;u++){
        int x=f[u],y=f[v];
        f[u]=(x+y)%mod,f[v]=1ll*w*(x-y+mod)%mod,w=1ll*w*wn%mod;
      }
    }
  }
}
void DIT(int n,int f[]){
  for(int i=2;i<=n;i<<=1){
    int wn=qpow(3,(mod-1)/i,mod);
    for(int j=0;j<n;j+=i){
      int w=1;
      for(int u=j,v=j+i/2;u<j+i/2;u++){
        int x=f[u],y=f[v];
        f[u]=(x+y)%mod,f[v]=(x-y+mod)%mod,w=1ll*w*wn%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];
  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];
}

评测结果