#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(a,b,c) for(register int a=b;a<=c;++a)
using namespace std;
namespace FFT {
const int N=270000;
const double pi=acos(-1);
struct cp {
double x,y;
cp operator + (const cp &_) {return (cp){x+_.x,y+_.y};}
cp operator - (const cp &_) {return (cp){x-_.x,y-_.y};}
cp operator * (const cp &_) {return (cp){x*_.x-y*_.y,x*_.y+y*_.x};}
}A[N],B[N],W[N];
int R[N];
void DFT(cp *a,int n,int p){
For(i,0,n-1) if(i<R[i]) swap(a[i],a[R[i]]);
W[0]=(cp){1,0};
for(register int i=1;i<n;i<<=1){
cp wn=(cp){cos(pi/i),p*sin(pi/i)};
for(register int j=i-2;j>=0;j-=2) W[j+1]=wn*(W[j]=W[j>>1]);
for(register int j=0;j<n;j+=i<<1){
cp *p=a+j,*q=a+i+j;
For(k,0,i-1){
cp x=W[k]*q[k];
q[k]=p[k]-x;
p[k]=p[k]+x;
}
}
}
}
void Mul (int *_A,int a,int *_B,int b) {
int n=(1<<(int)log2(a+b)<<1);
For(i,0,n-1) R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
For(i,0,a-1) A[i].x=_A[i];
For(i,0,b-1) A[i].y=_B[i];
DFT(A,n,1);
For(i,0,n-1) A[i]=A[i]*A[i];
DFT(A,n,-1);
For(i,0,n-1) _A[i]=A[i].y/n/2+0.5;
}
}
using FFT::Mul;
const int N=100007;
int A[N],B[N],a,b;
int main () {
scanf("%d%d",&a,&b),++a,++b;
For(i,0,a-1) scanf("%d",&A[i]);
For(i,0,b-1) scanf("%d",&B[i]);
Mul(A,a,B,b);
For(i,0,a+b-2) printf("%d ",A[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 37.24 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 47.648 ms | 9 MB + 232 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 21.228 ms | 4 MB + 596 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 21.214 ms | 4 MB + 200 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 40.37 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 38.54 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 38.46 us | 56 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 42.083 ms | 8 MB + 988 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 41.812 ms | 8 MB + 860 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 36.44 ms | 8 MB + 592 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 48.164 ms | 9 MB + 312 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 48.047 ms | 8 MB + 192 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 37.63 us | 56 KB | Accepted | Score: 0 | 显示更多 |