#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
struct cp
{
double a,b;
cp(double ai=0,double bi=0){a=ai,b=bi;}
cp operator+(cp x){return cp(a+x.a,b+x.b);}
cp operator-(cp x){return cp(a-x.a,b-x.b);}
cp operator*(cp x){return cp(a*x.a-b*x.b,a*x.b+b*x.a);}
cp operator/(cp x){return cp((a*x.a+b*x.b)/(x.a*x.a+x.b*x.b),(b*x.a-a*x.b)/(x.a*x.a+x.b*x.b));}
cp operator+=(cp x){return *this=*this+x;}
cp operator-=(cp x){return *this=*this-x;}
cp operator*=(cp x){return *this=*this*x;}
cp operator/=(cp x){return *this=*this/x;}
};
const int MAXN=4e6+10;
cp a[MAXN],b[MAXN];
int n,m,lim;
void fft(cp *a,int lim,int type)
{
if(lim==1)return;
int hl=lim>>1;cp a1[hl],a2[hl];
for(int i=0;i<hl;i++)a1[i]=a[i<<1],a2[i]=a[i<<1|1];
fft(a1,hl,type),fft(a2,hl,type);
cp wi(cos(pi*2/lim),type*sin(pi*2/lim)),w(1,0);
for(int i=0;hl>i;i++,w*=wi)
a[i]=a1[i]+w*a2[i],a[i+hl]=a1[i]-w*a2[i];
}
int main()
{
scanf("%d%d",&n,&m);n++,m++;
for(int i=0,ai;n>i;i++)scanf("%d",&ai),a[i]=cp(ai,0);
for(int j=0,bi;m>j;j++)scanf("%d",&bi),b[j]=cp(bi,0);
lim=1;
while(lim<=n+m)lim<<=1;
fft(a,lim,1),fft(b,lim,1);
for(int i=0;lim>i;i++)a[i]*=b[i];
fft(a,lim,-1);
for(int i=0;n+m-1>i;i++)
printf("%d ",int(a[i].a/lim+0.5));
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 13.678 ms | 122 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 114.409 ms | 131 MB + 536 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 60.44 ms | 126 MB + 388 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 60.624 ms | 126 MB + 376 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 13.676 ms | 122 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 13.677 ms | 122 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 14.413 ms | 122 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 109.318 ms | 131 MB + 268 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 108.519 ms | 131 MB + 268 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 102.622 ms | 131 MB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 114.918 ms | 131 MB + 616 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 115.648 ms | 130 MB + 496 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 14.041 ms | 122 MB + 108 KB | Accepted | Score: 0 | 显示更多 |