#include<algorithm>
#include<cstdio>
#define G 3
using namespace std;
const int P=998244353;
int n,m,s,ln,sl,fh,inv,a[5500010],b[5500010],rev[5500010];
int rd()
{
sl=0;fh=1;
char ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
return sl*fh;
}
int _pow(int k,int i)
{
int t=1;
while(i)
{
if(i&1) t=1ll*t*k%P;
k=1ll*k*k%P;i>>=1;
}
return t;
}
void NTT(int *e,int flg)
{
for(int i=0;i<ln;++i)
if(i<rev[i])
swap(e[i],e[rev[i]]);
int t,wn,fx,fy;
for(int i=2,mid=1;i<=ln;i<<=1,mid<<=1)
{
wn=_pow(G,(P-1)/i); if(flg==-1) wn=_pow(wn,P-2);
for(int j=0;j<ln;j+=i)
{
t=1;
for(int k=j;k<j+mid;++k,t=1ll*t*wn%P)
{
fx=e[k];fy=1ll*t*e[k+mid]%P;
e[k]=(fx+fy)%P;
e[k+mid]=(fx-fy+P)%P;
}
}
}
}
int main()
{
n=rd();m=rd();ln=1;
while(ln<=n+m) ln<<=1,s++;inv=_pow(ln,P-2);
for(int i=1;i<ln;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<s-1);
for(int i=0;i<=n;++i) a[i]=rd();
for(int i=0;i<=m;++i) b[i]=rd();
NTT(a,1);NTT(b,1);for(int i=0;i<ln;++i) a[i]=1ll*a[i]*b[i]%P;NTT(a,-1);
for(int i=0;i<=n+m;++i) printf("%d ",1ll*a[i]*inv%P);puts("");
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 9.73 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 70.579 ms | 4 MB + 456 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 32.366 ms | 1 MB + 820 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 32.469 ms | 1 MB + 808 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 10.76 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 12.71 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 9.42 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 65.429 ms | 4 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 65.427 ms | 4 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 60.25 ms | 3 MB + 944 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 70.843 ms | 4 MB + 536 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 70.986 ms | 3 MB + 416 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 7.38 us | 28 KB | Accepted | Score: 0 | 显示更多 |