代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,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++,v++){
        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++,v++){
        int x=f[u],y=1ll*w*f[v]%mod;
        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;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>n>>m;
  for(int i=0;i<=n;i++)cin>>f[i];
  for(int i=0;i<=m;i++)cin>>g[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++)cout<<h[i]<<(i==n+m?'\n':' ');
  return 0;
}

评测结果