#pragma GCC optimize("Ofast")
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1<<17;
typedef double flo;
typedef long long ll;
const flo pi=acos(-1.);
struct vec{
flo x,y;
vec(){}
vec(flo x,flo y=0):x(x),y(y){}
};
vec operator+(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator-(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator*(vec a,vec b){return vec(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
vec conj(vec a){return vec(a.x,-a.y);}
vec w[N];
void initw(int n){
w[1]=vec(1,0);
for(int i=2;i<n;i<<=1){
flo t=pi/i;
vec u(cos(t),sin(t));
for(int j=0;j<i/2;j++)
w[i+j*2+1]=(w[i+j*2]=w[i/2+j])*u;
}
}
vec*getw(int n){
return w+n/2;
}
void fft(vec*a,int n){
for(int i=0,j=0;i<n;++i){
if(i<j)
swap(a[i],a[j]);
for(int k=n>>1;;k>>=1)
if((j^=k)>=k)break;
}
for(int i=1;i<n;i<<=1){
vec*w=getw(i<<1);
for(int j=0;j<n;j+=i<<1){
vec*b=a+j,*c=b+i;
for(int k=0;k<i;++k){
vec v=w[k]*c[k];
c[k]=b[k]-v,b[k]=b[k]+v;
}
}
}
}
struct buf{
char a[1<<25],*s;
char b[1<<25],*t;
buf():s(a),t(b){
a[fread(a,1,sizeof a,stdin)]=0;
}
~buf(){fwrite(b,1,t-b,stdout);}
operator int(){
int x=0;
while(*s<48)++s;
while(*s>32)
x=x*10+*s++-48;
return x;
}
void out(int x){
static char c[12];
char*i=c;
if(!x)*t++=48;
else{
while(x){
int y=x/10;
*i++=x-y*10+48,x=y;
}
while(i!=c)*t++=*--i;
}
*t++=32;
}
}it;
int main(){
static ll a[N],b[N],c[N];
int n=it,m=it,n2=(n+1)/2,m2=m/2,u=m-m/2;
const int L=23;
for(int i=0;i<=n;++i)
a[i]=it;
for(int i=0;i<=n2;++i)
a[i]=a[i*2+1]<<L|a[i*2];
for(int i=n2+1;i<=n;++i)
a[i]=0;
for(int i=0;i<=m;++i)
b[i]=it;
for(int i=0;i<=u;++i)
c[i]=b[i*2+1];
for(int i=0;i<=m2;++i)
b[i]=b[i*2];
for(int i=m2+1;i<=m;++i)
b[i]=0;
if(n==0&&m==0)return it.out(a[0]*b[0]),0;
int l=2<<__lg(n2+u+1)-1;
static vec sa[N/2],sb[N/2],sc[N/2],sd[N/2],se[N/2];
for(int i=0;i<l;++i){
sa[i]=vec(a[i*2],a[i*2+1]);
sb[i]=vec(b[i*2],b[i*2+1]);
sc[i]=vec(c[i*2],c[i*2+1]);
}
initw(l);
fft(sa,l),fft(sb,l),fft(sc,l);
vec*w=getw(l);
#define tmul(a,b,c) c[j]=(conj(a[j]*b[j])*4-(conj(a[j])-a[i])*(conj(b[j])-b[i])*((i<l/2?w[i]:w[i-l/2]*-1)+1))*vec(0,.25);
for(int i=0;i<l;++i){
int j=l-i&l-1;
tmul(sa,sb,sd);
}
for(int i=0;i<l;++i){
int j=l-i&l-1;
tmul(sa,sc,se);
}
fft(sd,l);
fft(se,l);
for(int i=0;i<l;++i)
a[i*2]=sd[i].y/l+.5,a[i*2+1]=sd[i].x/l+.5,
b[i*2]=se[i].y/l+.5,b[i*2+1]=se[i].x/l+.5;
u=(n+m-1)/2;
for(int i=0;i<=u;++i)
{
b[i]+=a[i]>>23;
it.out(a[i]&0x7fffff);
a[i+1]+=b[i]>>23;
it.out(b[i]&0x7fffff);
}
if(!(n+m&1))it.out(a[u+1]&0x7fffff);
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 15.67 us | 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 14.274 ms | 11 MB + 652 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 10.024 ms | 5 MB + 456 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #4 | 10.039 ms | 5 MB + 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 15.9 us | 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 15.44 us | 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 15.57 us | 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 13.598 ms | 11 MB + 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 22.121 ms | 10 MB + 940 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 12.912 ms | 10 MB + 336 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 22.978 ms | 11 MB + 812 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 11.826 ms | 9 MB + 568 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 11.52 us | 48 KB | Accepted | Score: 0 | 显示更多 |