#include<bits/stdc++.h>
using namespace std;
typedef vector<int> poly;
const int maxn=270003;
const double pi=acos(-1);
struct com{
double r,i;
com(){}
com(double _r,double _i):r(_r),i(_i){}
com operator+(const com &x)const{return com(r+x.r,i+x.i);}
com operator-(const com &x)const{return com(r-x.r,i-x.i);}
com operator*(const com &x)const{return com(r*x.r-i*x.i,r*x.i+i*x.r);}
}k1[maxn],k2[maxn];
int r[maxn];
void fft(com a[],int n,int sgn){
for(int i=0;i<n;i++)if(r[i]>i)swap(a[i],a[r[i]]);
for(int mid=1;mid<n;mid<<=1){
com wn(cos(pi/mid),sgn*sin(pi/mid));
for(int j=0;j<n;j+=(mid<<1)){
com w(1,0);
for(int k=0;k<mid;k++,w=w*wn){
com tmp=w*a[j+k+mid];
a[j+k+mid]=a[j+k]-tmp;
a[j+k]=a[j+k]+tmp;
}
}
}
}
poly operator*(const poly &a,const poly &b){
int n1=a.size()-1,n2=b.size()-1,lg=0,n=1;
while(n<=n1+n2)lg++,n<<=1;
for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));
for(int i=0;i<=n1;i++)k1[i].r=a[i];
for(int i=0;i<=n2;i++)k2[i].r=b[i];
fft(k1,n,1);
fft(k2,n,1);
for(int i=0;i<n;i++)k1[i]=k1[i]*k2[i];
fft(k1,n,-1);
poly ret(n1+n2+1);
for(int i=0;i<=n1+n2;i++)ret[i]=k1[i].r/n+0.5;
return ret;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
poly a(n+1),b(m+1);
for(int i=0;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<=m;i++)scanf("%d",&b[i]);
a=a*b;
a.resize(n+m+1);
for(int i=0;i<a.size();i++)printf("%d ",a[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 37.79 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 66.247 ms | 11 MB + 1012 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 29.499 ms | 5 MB + 596 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 29.62 ms | 5 MB + 584 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 40.03 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 39.26 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 38.03 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 60.829 ms | 11 MB + 476 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 60.261 ms | 11 MB + 476 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 54.603 ms | 10 MB + 960 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 66.314 ms | 12 MB + 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 66.947 ms | 10 MB + 972 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 36.53 us | 48 KB | Accepted | Score: 0 | 显示更多 |