//仅用于测试
#include<cmath>
#include<cstdio>
#include<algorithm>
#define mod 998244353
#define gg 3
#define ll long long
#define N 440000
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x*f;
}
inline int ksm(int base,int t){
int tmp=1;
for (;t;t>>=1,base=(ll)base*base%mod) if (t&1) tmp=(ll)tmp*base%mod;return tmp;
}
int n,m,R[N],a[N],b[N];
inline void ntt(int *x,int f){
for (int i=0;i<n;++i) if (i<R[i]) swap(x[i],x[R[i]]);
for (int i=1;i<n;i<<=1){
ll wn=ksm(gg,f==1?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
for (int j=0;j<n;j+=(i<<1)){
ll w=1;
for (int k=0;k<i;++k,(w*=wn)%=mod){
int t1=x[j+k],t2=x[j+i+k];t2=(ll)t2*w%mod;
x[j+k]=t1+t2>mod?t1+t2-mod:t1+t2;
x[j+i+k]=t1-t2<0?t1-t2+mod:t1-t2;
}
}
}
}
int main(){
n=read();m=read();
for (int i=0;i<=n;++i) a[i]=read();
for (int i=0;i<=m;++i) b[i]=read();m=n+m;for (n=1;n<=m;n<<=1);int l=log2(n);
for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<l-1);
ntt(a,1);ntt(b,1);
for (int i=0;i<n;++i) a[i]=(ll)a[i]*b[i]%mod;
ntt(a,-1);int inv=ksm(n,mod-2);
for (int i=0;i<n;++i) a[i]=(ll)a[i]*inv%mod;
for (int i=0;i<=m;++i) printf("%d ",a[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 9.66 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 63.859 ms | 4 MB + 516 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 29.157 ms | 1 MB + 880 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 29.232 ms | 1 MB + 868 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 10.45 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 10.06 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 10.17 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 58.931 ms | 4 MB + 248 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 58.831 ms | 4 MB + 248 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 53.777 ms | 3 MB + 1004 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 64.083 ms | 4 MB + 596 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 64.551 ms | 3 MB + 476 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 8.96 us | 28 KB | Accepted | Score: 0 | 显示更多 |