#include<bits/stdc++.h>
using namespace std;
const int maxn=262148;//262144=1<<17
struct cp{
double r,i;
}w[maxn],a[maxn],b[maxn];
inline cp operator + (const cp &x,const cp &y){
return (cp){x.r+y.r,x.i+y.i};
}
inline cp operator - (const cp &x,const cp &y){
return (cp){x.r-y.r,x.i-y.i};
}
inline cp operator * (const cp &x,const cp &y){
return (cp){x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r};
}
int N,rev[maxn];
const double pi=acos(-1);
inline void init(int n){
int bit=0;
for(N=1;N<=n;N<<=1) bit++;
for(int i=0;i<N;i++) w[i]=(cp){cos(2*pi*i/N),sin(2*pi*i/N)};
for(int i=0;i<(1<<bit);i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
inline void fft(cp *x,int v){
if(v) for(int i=1;i<N;i++) if(i<N-i) swap(x[i],x[N-i]);
for(int i=0;i<N;++i) if(i<rev[i])swap(x[i],x[rev[i]]);
for(int i=1;i<N;i<<=1){
for(int j=0;j<N;j+=i<<1){
for(int k=0;k<i;++k){
cp p=w[N/(i<<1)*k]*x[i+j+k];
x[i+j+k]=x[j+k]-p;x[j+k]=x[j+k]+p;
}
}
}
if(v)for(int i=0;i<N;++i)x[i].r/=N,x[i].i/=N;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) scanf("%lf",&a[i].r);
for(int i=0;i<=m;i++) scanf("%lf",&b[i].r);
init(n+m);
fft(a,0);fft(b,0);
for(int i=0;i<N;i++) a[i]=a[i]*b[i];
fft(a,1);
for(int i=0;i<=n+m;++i)printf("%d ",(int)(a[i].r+0.5));
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 37.61 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 76.718 ms | 14 MB + 472 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 33.34 ms | 6 MB + 852 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #4 | 33.262 ms | 6 MB + 840 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 41.87 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 39.61 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 38.77 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 70.654 ms | 14 MB + 204 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 70.165 ms | 14 MB + 204 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 64.297 ms | 13 MB + 960 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 76.437 ms | 14 MB + 552 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 76.036 ms | 13 MB + 432 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 36.84 us | 60 KB | Accepted | Score: 0 | 显示更多 |