#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e6+5;
const int P=119<<23|1,G=3;
ll eps[N],a[N],b[N];
ll qpow(ll x,ll y){
ll ans=1;
for(;y;y>>=1){
if(y&1)ans=ans*x%P;
x=x*x%P;
}
return ans;
}
ll inv(ll x){
return qpow(x,P-2);
}
void init(int n){
ll g=qpow(G,(P-1)/n);
int l=n>>1;
eps[l]=1;
for(int i=1;i<l;++i){
eps[l+i]=eps[l+i-1]*g%P;
}
while(l>>=1){
for(int i=0;i<l;++i){
eps[l+i]=eps[l+i<<1];
}
}
}
void dft(int n,ll x[]){
for(int i=0,j=0;i<n;++i){
if(i<j)swap(x[i],x[j]);
for(int k=n>>1;(j^=k)<k;k>>=1){}
}
for(int i=2;i<=n;i<<=1){
int l=i>>1;
for(int j=0;j<n;j+=i){
for(int k=0;k<l;++k){
ll u=x[j+k],v=eps[l+k]*x[j+k+l]%P;
x[j+k]=(u+v)%P;
x[j+k+l]=(u-v+P)%P;
}
}
}
}
void idft(int n,ll x[]){
reverse(x+1,x+n);
dft(n,x);
ll in=inv(n);
for(int i=0;i<n;++i)x[i]=x[i]*in%P;
}
int main(){
#ifdef LOCAL
freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<=n;++i)cin>>a[i];
for(int i=0;i<=m;++i)cin>>b[i];
int len=1;
while(len<n+m+2)len<<=1;
init(len);
dft(len,a),dft(len,b);
for(int i=0;i<len;++i)(a[i]*=b[i])%=P;
idft(len,a);
for(int i=0;i<=n+m;++i)cout<<a[i]<<' ';
return 0;
}
Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |