代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int mod=998244353, gen=3;

ll jc[202000], inv[202000];
int k=1e9, p[202000], used[202000];

ll K(ll x,ll y=mod-2){
  ll t=1;
  for (;y;y>>=1, x=x*x%mod)
    if (y&1) t=t*x%mod;
  return t;
}

namespace FFT{
  int mx=0, dp[270000], W[18][270000];

  inline int up(int x){
    return x>=mod? x-mod: x;
  }
  
  void dft(int *a,int n){
    if (n>mx){
      for (int i=mx;i<n;++i){
	ll w=1, b=K(gen,(mod-1)/(1<<i+1));
	for (int j=0;j<(1<<i);++j){
	  W[i][j]=w; w=w*b%mod;
	}
      }
      mx=n;
    }
    for (int i=1;i<1<<n;++i){
      dp[i]= i&1? dp[i^1]|1<<n-1: dp[i>>1]>>1;
      if (i<dp[i]) swap(a[i],a[dp[i]]);
    }
    for (int b=0;b<n;++b){
      for (int i=0;i<1<<n;i+=1<<(b+1)){
	int *l=a+i, *r=a+i+(1<<b);
	for (int j=0;j<1<<b;++j){
	  int x=l[j], y=(ll)r[j]*W[b][j]%mod;
	  l[j]=up(x+y); r[j]=up(x-y+mod);
	}
      }
    }
  }
  void idft(int *a,int n){
    reverse(a+1,a+(1<<n)); dft(a,n); ll inv=K(1<<n);
    for (int i=0;i<1<<n;++i) a[i]=a[i]*inv%mod;
  }
}

void mg(vector<int>&a,vector<int>&b){
  static int A[270000], B[270000], n, la, lb;
  la=a.size()-1; lb=b.size()-1;
  for (n=0;(1<<n)<=la+lb;++n);
  for (int i=0;i<1<<n;++i){
    A[i]= i<=la? a[i]: 0;
    B[i]= i<=lb? b[i]: 0;
  }
  FFT::dft(A,n); FFT::dft(B,n);
  for (int i=0;i<1<<n;++i) A[i]=(ll)A[i]*B[i]%mod;
  FFT::idft(A,n);
  a.clear();
  for (int i=0;i<=min(la+lb,k);++i) a.push_back(A[i]);
}

ll C(int x,int y){
  return jc[x] *inv[y]%mod *inv[x-y]%mod;
}


vector<int>vec[202000], a, b;

int n, m;

int main(){
  scanf("%d%d",&n,&m); int x;
  for (int i=0;i<=n;++i) scanf("%d",&x), a.push_back(x);
  for (int i=0;i<=m;++i) scanf("%d",&x), b.push_back(x);
  mg(a,b);
  for (int i=0;i<=n+m;++i) printf("%d ",a[i]); puts("");
}

评测结果