#include<cstdio>
#include<cstring>
#define mod 998244353
typedef long long LL;
int W[2][262144],_i[19];
inline int fmo(int a,int b)
{
return (LL)a*b%mod;
}
inline int ksm(LL a,LL b){int r=1;for(;b;a=fmo(a,a),b>>=1)if(b&1)r=fmo(r,a);return r;}
void NTT_Init()
{
int i,j,t,*x;
for(i=1;i<262144;i<<=1)
{
W[0][i] = 1, t = ksm(3,(mod-1)/i/2);
for(j=1;j<i;j++)W[0][i+j] = fmo(W[0][i+j-1],t);
W[1][i] = 1, t = ksm(332748118,(mod-1)/i/2);
for(j=1;j<i;j++)W[1][i+j] = fmo(W[1][i+j-1],t);
}
for(_i[0]=i=1;i<19;i++)_i[i] = fmo(_i[i-1],499122177);
}
void NTT(int *f,int len,int sign)
{
int i,j,k,*w,*p,*q,t;sign=sign==-1;
for(i=j=0;i<len;i++){if(i<j)f[i]^=f[j]^=f[i]^=f[j];for(k=len>>1;(j^=k)<k;k>>=1);}
for(i=1;i<len;i<<=1)for(j=0;j<len;j+=i<<1)for(w=W[sign]+i,q=(p=f+j)+i,k=0;k<i;k++)
{t=fmo(*q,*w++);if((*q=*p-t)<0){*q+=mod;}if((*p+=t)>=mod){*p-=mod;}p++,q++;}
if(sign)for(k=_i[__builtin_ctz(len)],i=0;i<len;i++)f[i] = fmo(k,f[i]);
}
int a[262144],b[262144];
int main()
{
int n,m,i,l;
NTT_Init();
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)scanf("%d",a+i);
for(i=0;i<=m;i++)scanf("%d",b+i);
n = n+m+1;
for(l=1;l<n;l<<=1);
NTT(a,l,1), NTT(b,l,1);
for(i=0;i<l;i++)a[i] = fmo(a[i],b[i]);
NTT(a,l,-1);
for(i=0;i<n;i++)printf("%d ",a[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 2.737 ms | 2 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 56.556 ms | 5 MB + 444 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 27.313 ms | 3 MB + 304 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 27.341 ms | 3 MB + 292 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 2.738 ms | 2 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 2.736 ms | 2 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 2.736 ms | 2 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 50.718 ms | 5 MB + 176 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 50.948 ms | 5 MB + 176 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 45.183 ms | 4 MB + 932 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 56.788 ms | 5 MB + 524 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 56.869 ms | 4 MB + 404 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 2.736 ms | 2 MB + 24 KB | Accepted | Score: 0 | 显示更多 |