C++(clang++ 11.0.1) 解法, 执行用时: 934ms, 内存消耗: 14712K, 提交时间: 2023-08-10 11:43:31

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=6e5+10,mod=998244353,G=3,inv_G=332748118;
int fac[N],inv[N];
int a[N],b[N];
int qz(int x,int y){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
void init(int n){
	int i;
	fac[1]=1;
	For(i,2,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=qz(fac[n],mod-2);
	FOR(i,n-1,0) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y){
	return (fac[x]*inv[y]%mod)*inv[x-y]%mod;
}
int rev[N];
void ntt(vector<int> &a,int sign,int tot){
	int i,j,mid;
	For(i,0,tot-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(mid=1;mid<tot;mid<<=1){
		auto g1=qz(G,(mod-1)/(mid<<1));
		if(sign==-1) g1=qz(inv_G,(mod-1)/(mid<<1));
		for(i=0;i<tot;i+=(mid<<1)){
			auto gk=1; 
			for(j=0;j<mid;j++,gk=gk*g1%mod){
				auto x=a[i+j],y=gk*a[i+j+mid]%mod;
				a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
			}
		}
	}
	int inv=qz(tot,mod-2);
	if(sign==-1) For(i,0,tot-1) a[i]=a[i]*inv%mod;
}
vector<int> solve(int l,int r){
	int i,mid=l+r>>1;
	if(l==r){
		vector<int> t(a[l]+1);
		t[0]=((qz(2,b[l])-1)%mod+mod)%mod;
		For(i,1,a[l]) t[i]=C(a[l],i);
		return t;
	}
	auto L=solve(l,mid);
	auto R=solve(mid+1,r);
	int tot,bit=0,lenL=L.size(),lenR=R.size();
	while((1<<bit)<=lenL+lenR) bit++;
	tot=1<<bit;
	L.resize(tot);
	R.resize(tot);
	For(i,0,tot-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	ntt(L,1,tot),ntt(R,1,tot);
	For(i,0,tot-1) L[i]=L[i]*R[i]%mod;
	ntt(L,-1,tot);
	L.resize(lenL+lenR-1);
	return L;
}
signed main(){
	int n,i,tot=0;
	init(2e5);
	cin>>n;
	For(i,1,n) cin>>a[i];
	For(i,1,n) cin>>b[i];
	auto ans=solve(1,n);
	For(i,1,n) tot+=a[i];
	For(i,0,tot) cout<<ans[i]<<' ';
	return 0;
}