#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const double PI=acos(-1);
int n,m,s,sl,fh,len,f[6000010];
struct node
{
double x,y;
node(double _x=0,double _y=0) {x=_x,y=_y;}
}a[6000010],b[6000010];
node operator -(node k1,node k2)
{
return node(k1.x-k2.x,k1.y-k2.y);
}
node operator +(node k1,node k2)
{
return node(k1.x+k2.x,k1.y+k2.y);
}
node operator *(node k1,node k2)
{
return node(k1.x*k2.x-k1.y*k2.y,k1.x*k2.y+k1.y*k2.x);
}
int rd()
{
sl=0;fh=1;
char ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='0') fh=-1; ch=getchar();}
while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
return sl*fh;
}
void FFT(node *e,double k)
{
for(int i=0;i<=s;++i)
if(i<f[i])
swap(e[i],e[f[i]]);
node fx,fy;
for(int i=2,mid=1;i<=s;i<<=1,mid<<=1)
{
node wn(cos(2.0*PI/i),k*sin(2.0*PI/i));
for(int j=0;j<s;j+=i)
{
node t(1,0);
for(int k=j;k<j+mid;k++,t=t*wn)
{
fx=e[k],fy=t*e[k+mid];
e[k]=fx+fy;
e[k+mid]=fx-fy;
}
}
}
}
int main()
{
n=rd()+1;m=rd()+1;
for(int i=0;i<n;++i) a[i].x=rd();
for(int i=0;i<m;++i) b[i].x=rd();
s=1;
while(s<n+m) s<<=1,len++;
for(int i=0;i<=s;++i) f[i]=(f[i>>1]>>1)|((i&1)<<len-1);
FFT(a,1);FFT(b,1);
for(int i=0;i<=s;++i) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<n+m-1;++i) printf("%d ",(int)(a[i].x/s+0.5));
puts("");
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 20.468 ms | 183 MB + 128 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 81.025 ms | 185 MB + 556 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 48.996 ms | 183 MB + 920 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 47.879 ms | 183 MB + 908 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 21.142 ms | 183 MB + 128 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 20.532 ms | 183 MB + 128 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 21.268 ms | 183 MB + 128 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 75.485 ms | 185 MB + 288 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 75.635 ms | 185 MB + 288 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 69.955 ms | 185 MB + 20 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 81.271 ms | 185 MB + 636 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 83.382 ms | 184 MB + 516 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 20.462 ms | 183 MB + 128 KB | Accepted | Score: 0 | 显示更多 |