// luogu-judger-enable-o2
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
struct complex{
double x,y;
complex operator+(complex a)const {return (complex){x+a.x,y+a.y};}
complex operator-(complex a)const {return (complex){x-a.x,y-a.y};}
complex operator*(complex a)const {return (complex){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[3000010],b[3000010];
int lim=1,l=0;
int where[3000010];
double co[3000010],si[3000010];
const double Pi=acos(-1.0)*2.0;
complex wn,w,fa,fb;
void dft(complex *now,int idft){
for(int i=0;i<lim;i++) if(where[i]>i) swap(now[i],now[where[i]]);
complex wn,w,a,b;
for(int l=2;l<=lim;l*=2){
wn=(complex){cos(Pi/l),idft*sin(Pi/l)};
for(int i=0;i<lim;i+=l){
w=(complex){1,0};
for(int x=i,y=i+l/2;y<i+l;x++,y++,w=w*wn){
a=now[x],b=now[y]*w;
now[x]=a+b;
now[y]=a-b;
}
}
}
}
int main(){
scanf("%d %d",&n,&m);n++;m++;
for(int i=0;i<n;i++) scanf("%lf",&a[i].x);
for(int i=0;i<m;i++) scanf("%lf",&b[i].x);
while(lim<n+m-1) lim*=2,l++,co[lim]=cos(Pi/lim),si[lim]=sin(Pi/lim);
for(int i=0;i<lim;i++) where[i]=((where[i>>1]>>1) | ((i&1)<<(l-1)));
dft(a,1);dft(b,1);
for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
dft(a,-1);
for(int i=0;i<n+m-1;i++) printf("%d ",(int)(a[i].x/lim+0.5));
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 38.05 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 65.218 ms | 10 MB + 572 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 29.988 ms | 4 MB + 928 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 30.048 ms | 4 MB + 916 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 41.2 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 38.92 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 38.89 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 59.304 ms | 10 MB + 304 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 59.329 ms | 10 MB + 304 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 53.509 ms | 10 MB + 36 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 65.588 ms | 10 MB + 652 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 65.38 ms | 9 MB + 532 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 37.04 us | 60 KB | Accepted | Score: 0 | 显示更多 |