#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define _SIZE_ 100000
char _b[_SIZE_],*_b1,*_b2;
#define getc() (_b1==_b2?fread(_b,1,_SIZE_,stdin),_b2=_b+_SIZE_,*((_b1=_b)++):*(_b1++))
#define read(__x) {register signed _x(0);register char _c=getc(),_f(0);for(;_c<47;_c=getc())_f=(_c==45);for(;_c>47;_c=getc())_x=_x*10+(_c^48);_f&&(_x=-_x),__x=_x;}
char _d[_SIZE_],*_p=_d;
#define putc(__c) (_p-_d==_SIZE_?fwrite(_d,1,_SIZE_,stdout),_p=_d,*_p++=__c:*_p++=__c)
#define write(__x) {register signed _x=__x;(_x<0)&&(putc(45),_x=-_x);static signed _q[11];register char _t=0;do{_q[_t++]=_x%10,_x/=10;}while(_x);while(_t)putc(_q[--_t]+48);}
#define fwflush() (fwrite(_d,1,_p-_d,stdout),_p=_d)
#define pi 3.14159265358979323846
struct C
{
double x,y;
C operator+(const C b)const{return {x+b.x,y+b.y};}
C operator-(const C b)const{return {x-b.x,y-b.y};}
C operator*(const C b)const{return {x*b.x-y*b.y,x*b.y+y*b.x};}
};
const int _lg2[]={0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3};
using namespace std;
int tmp1,n,m,N;
int lg2(int i)
{
int tmp(0);
if(i>65535)tmp|=16,i>>=16;
if(i>255)tmp|=8,i>>=8;
if(i>15)tmp|=4,i>>=4;
return tmp+_lg2[i];
}
double co[21],si[21];
void fft(C*a,int n)
{
if(n==1)return;
int mid=n>>1;
C b[n],x__={1,0},x_={co[lg2(n)],si[lg2(n)]};
//for(int i=0;i<mid;i++)b[i]=a[i<<1];
//for(int i=0;i<mid;i++)b[i|mid]=a[i<<1|1];
fft(b,mid),fft(b+mid,mid);
for(int i=0;i<mid;i++,x__=x__*x_)
{
C x(b[i+mid]*(C){x__.x,x__.y});
a[i]=b[i]+x,a[i+mid]=b[i]-x;
}
}
void ifft(C*a,int n)
{
if(n==1)return;
int mid=n>>1;
C b[n],x__={1,0},x_={co[lg2(n)],si[lg2(n)]};
//for(int i=0;i<mid;i++)b[i]=a[i<<1];
//for(int i=0;i<mid;i++)b[i|mid]=a[i<<1|1];
ifft(b,mid),ifft(b+mid,mid);
for(int i=0;i<mid;i++,x__=x__*x_)
{
C x(b[i+mid]*(C){x__.x,-x__.y});
a[i]=b[i]+x,a[i+mid]=b[i]-x;
}
}
C a[1<<21];
int main()
{
for(int i=0;i<=20;i++)co[i]=cos(2*pi/(1<<i)),si[i]=sin(2*pi/(1<<i));
read(n);read(m);++n,++m,N=min(1<<21,1<<(int)(log2(n+m)+1));
for(int i=0;i<n;i++)read(a[i].x);
for(int i=0;i<m;i++)read(a[i].y);
fft(a,N);
for(int i=0;i<N;i++)a[i]=a[i]*a[i];
ifft(a,N);
for(int i=0;i<n+m-1;i++){write((int)round(a[i].y/N/2));putc(32);}
fwflush();
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 36.72 us | 48 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 21.511 ms | 12 MB + 624 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 9.972 ms | 6 MB + 428 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 9.97 ms | 6 MB + 428 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 38.15 us | 48 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 36.44 us | 48 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 36.13 us | 48 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 21.212 ms | 12 MB + 556 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 21.213 ms | 12 MB + 556 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 20.921 ms | 12 MB + 492 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 21.487 ms | 12 MB + 624 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 21.485 ms | 12 MB + 624 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 36.94 us | 48 KB | Wrong Answer | Score: 0 | 显示更多 |