D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定两个分别为
n
n
n和
m
m
m次多项式，求它们的卷积
数据范围：
n
,
m
≤
1
0
6
n,m\leq 10^6
n,m≤106
S
o
l
u
t
i
o
n
Solution
Solution
FFT模板
C
o
d
e
Code
Code
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 4000010
using namespace std
;int n
,m
,l
,r
[N
],limit
=1;
const double Pi
=3.141592653589793;
inline long long read()
{
char c
;int d
=1;long long f
=0;
while(c
=getchar(),!isdigit(c
))if(c
==45)d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
struct complex
{
double x
,y
;
complex
(double xx
=0,double yy
=0){x
=xx
;y
=yy
;}
}a
[N
],b
[N
];
complex
operator +(complex a
,complex b
){return complex(a
.x
+b
.x
,a
.y
+b
.y
);}
complex
operator -(complex a
,complex b
){return complex(a
.x
-b
.x
,a
.y
-b
.y
);}
complex
operator *(complex a
,complex b
){return complex(a
.x
*b
.x
-a
.y
*b
.y
,a
.x
*b
.y
+a
.y
*b
.x
);}
inline void fft(complex
*A
,int op
)
{
for(register int i
=0;i
<limit
;i
++) if(i
<r
[i
]) swap(A
[i
],A
[r
[i
]]);
for(register int mid
=1;mid
<limit
;mid
<<=1)
{
complex
wn(cos(Pi
/mid
),op
*sin(Pi
/mid
));
for(register int R
=mid
<<1,j
=0;j
<limit
;j
+=R
)
{
complex
w(1,0);
for(register int k
=0;k
<mid
;k
++,w
=w
*wn
)
{
complex x
=A
[j
+k
],y
=w
*A
[j
+mid
+k
];
A
[j
+k
]=x
+y
;
A
[j
+mid
+k
]=x
-y
;
}
}
}
return;
}
signed main()
{
n
=read();m
=read();
for(register int i
=0;i
<=n
;i
++) a
[i
].x
=read();
for(register int i
=0;i
<=m
;i
++) b
[i
].x
=read();
while(limit
<=n
+m
) limit
<<=1,l
++;
for(register int i
=0;i
<limit
;i
++) r
[i
]=(r
[i
>>1]>>1)|((i
&1)<<(l
-1));
fft(a
,1);fft(b
,1);
for(register int i
=0;i
<=limit
;i
++) a
[i
]=a
[i
]*b
[i
];
fft(a
,-1);
for(register int i
=0;i
<=n
+m
;i
++) printf("%d ",(int)(a
[i
].x
/limit
+0.5));
}
