#include<bits/stdc++.h>
#define ll long long
#define vci vector<int>
using namespace std;
const int mod=998244353;
const int N=1<<21|5;
const int gen=3;
inline int fsp(int x,int y){
int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)(y&1)&&(ans=1ll*ans*x%mod);
return ans;
}namespace Math{
int tr=0,tw=2,tv=2,rev[N],w[N],iv[N];
inline void initrev(int x){
tr=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
}inline void initw(int x){(!w[1])&&(w[1]=1);
for(;tw<x;tw<<=1){
w[tw]=1;w[tw+1]=fsp(gen,mod/(tw<<1));
for(int i=tw+2;i<(tw<<1);++i)w[i]=1ll*w[i-1]*w[tw+1]%mod;
}
}inline void initiv(int x){(!iv[1])&&(iv[1]=1);
for(;tv<=x;++tv)iv[tv]=1ll*(mod-mod/tv)*iv[mod%tv]%mod;
}inline int ginv(int x){
(x<=1<<21)&&(initiv(x),0);
return x<tv?iv[x]:fsp(x,mod-2);
}inline void ntt(int* a,int lim,int fl=1){
static unsigned ll A[N];initw(lim);
(tr!=lim)&&(initrev(lim),0);
for(int i=0;i<lim;i++)A[i]=a[rev[i]];
for(int k=1;k<lim;k<<=1){
if(k==1<<18)for(int i=0;i<lim;++i)A[i]%=mod;
for(int j=0;j<lim;j+=k<<1)for(int i=j,t;i<j+k;++i)
A[i+k]=A[i]+mod-(t=A[i+k]*w[i+k-j]%mod),A[i]+=t;
}if(fl^1){reverse(A+1,A+lim);for(int i=0,niv=ginv(lim);i<lim;i++)a[i]=A[i]*niv%mod;}
else for(int i=0;i<lim;i++)a[i]=A[i]%mod;
}
}namespace Poly{
using Math::ntt;
int A[N];
struct poly{
vci f;poly(int x=0){f.clear();(x)&&(f.push_back(x),0);}
poly(int *a,int n){f.resize(n);memcpy(f.data(),a,n<<2);}
inline int operator [](int x)const{return x<f.size()?f[x]:0;}
inline int& operator [](int x){return f.at(x);}
inline int* data(){return f.data();}inline const int* data()const{return f.data();}
inline int size()const{return f.size();}inline void resize(int x){return f.resize(x);}
inline poly& operator *=(const poly& a){
int lim=1;while(lim<size()+a.size()-1)lim<<=1;
resize(lim);memcpy(A,a.data(),a.size()<<2);ntt(data(),lim);ntt(A,lim);
for(int i=0;i<lim;i++)f[i]=1ll*f[i]*A[i]%mod;
ntt(data(),lim,0);return *this;
}inline poly operator *(const poly& a)const{poly b(*this);(b*=a).resize(size()+a.size()-1);return b;}
inline void print(char ch=' ')const{
for(int i=0;i<size();++i,putchar(ch))printf("%d",f[i]);
putchar('\n');
}
};
}
using Poly::poly;
int n,m,a[N],b[N];
poly f;
int main(){
scanf("%d%d",&n,&m);++n;++m;
for(int i=0;i<n;i++)scanf("%d",a+i);
for(int i=0;i<m;i++)scanf("%d",b+i);
(poly(a,n)*poly(b,m)).print();
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 38.67 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 46.971 ms | 10 MB + 392 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 20.435 ms | 4 MB + 612 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 20.405 ms | 4 MB + 996 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 40.99 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 39.97 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 39.65 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 42.056 ms | 9 MB + 748 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 41.918 ms | 9 MB + 884 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 36.934 ms | 9 MB + 212 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 47.306 ms | 10 MB + 472 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 46.938 ms | 9 MB + 352 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 38.31 us | 64 KB | Accepted | Score: 0 | 显示更多 |