#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<utility>
#define lol long long
#define mp make_pair
#define ft first
#define sc second
using namespace std;
typedef pair<double,double> cpx;
const int M = 1008611;
const double _2pi = 2.0 * acos(-1);
char s1[M],s2[M];
stack<char> ans;
int n,m,l;
cpx operator +(const cpx &a,const cpx &b)
{
return mp(a.ft + b.ft,a.sc + b.sc);
}
cpx operator -(const cpx &a,const cpx &b)
{
return mp(a.ft - b.ft,a.sc - b.sc);
}
cpx operator *(const cpx &a,const cpx &b)
{
return mp(a.ft * b.ft - a.sc * b.sc ,a.ft * b.sc + a.sc * b.ft);
}
cpx va[M],vb[M],vc[M];
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
void sread()
{
int a;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
a = read();
va[i].ft = (double) a;
va[i].sc = 0.0;
}
for(int i=0;i<=m;i++)
{
a = read();
vb[i].ft = (double) a;
vb[i].sc = 0.0;
}
if(n < m)
{
swap(n,m);
swap(va,vb);
}
int t = n + m + 2;
t <<= 1;
for(l=1;l<t;l <<= 1);
}
void pre(int l,int r,cpx *v)
{
if(l < r)
{
int mid = l + r >> 1;
static cpx dl[M],dr[M];
for(int i=l;i < r;i += 2)
{
dl[(i - l) >> 1] = v[i];
dr[(i - l) >> 1] = v[i + 1];
}
memcpy(v + l,dl,(mid - l + 1) * sizeof(cpx));
memcpy(v + mid + 1,dr,(r - mid) * sizeof(cpx));
pre(l,mid,v);
pre(mid + 1,r,v);
}
}
void fft(cpx *v,int l,bool flg)
{
const double pi2 = flg ? _2pi : -_2pi;
for(int k = 2;k <=l ;k <<= 1)
{
cpx wn = mp(cos(pi2 / k),sin(pi2 / k));
for(int i = 0;i < l; i += k)
{
cpx w = mp(1.0,0.0);
for(int j = 0;j < k >> 1;j++)
{
cpx t1 = v[i + j],t2 = v[i + j + (k >> 1)] * w;
v[i + j] = t1 + t2;
v[i + j + (k >> 1)] = t1 - t2;
w = w * wn;
}
}
}
if(!flg)
{
cpx inv = mp(1.0 / l,0.0);
for(int i = 0; i < l;i++)
{
v[i] = v[i] * inv;
}
}
}
void print()
{
for(int i=0;i<=n+m;i++)
{
printf("%d ",(int)(vc[i].ft + 0.5));
}
}
int main()
{
sread();
pre(0,l-1,va);
fft(va,l,true);
pre(0,l-1,vb);
fft(vb,l,true);
for(int i=0;i<l;i++) vc[i] = va[i] * vb[i];
pre(0,l-1,vc);
fft(vc,l,false);
print();
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 39.97 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 159.414 ms | 33 MB + 492 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 75.275 ms | 39 MB + 108 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 70.746 ms | 16 MB + 332 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 41.15 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 5.273 ms | 30 MB + 852 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 40.88 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 157.921 ms | 47 MB + 1012 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 154.375 ms | 33 MB + 224 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 148.785 ms | 32 MB + 980 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 159.376 ms | 33 MB + 572 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 159.65 ms | 32 MB + 452 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 39.32 us | 64 KB | Accepted | Score: 0 | 显示更多 |