[洛谷 3803]【模板】多项式乘法（FFT）

• 2018-02-14
• 0
• 0

Problem:

输入输出样例

```1 2
1 2
1 2 1```

`1 4 5 2`

FFT 模板题。

Code: O(klogk), 其中k=max{n,m} [98667K, 1824MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const double PI = acos(-1.0);

inline int getint(){
char ch; int num;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
return num;
}

struct Complex{
double r, i;

Complex(): r(0), i(0) {}
Complex(double r, double i): r(r), i(i) {}

inline Complex operator + (const Complex &c) const {return Complex(r + c.r, i + c.i);}
inline Complex operator - (const Complex &c) const {return Complex(r - c.r, i - c.i);}
inline Complex operator * (const Complex &c) const {return Complex(r * c.r - i * c.i, r * c.i + i * c.r);}
};

int n, m, k;
Complex a[2100000], b[2100000], omega[2100000];

inline void FFT(Complex a[], int f){
for(register int i = 0, j = 0; i < k; i++){
if(i > j) swap(a[i], a[j]);
for(register int l = k >> 1; (j ^= l) < l; l >>= 1);
}  // 二进制序号反转
for(register int i = 1; i < k; i <<= 1){  // 半平面被分成的部分数
omega[0] = Complex(1, 0), omega[1] = Complex(cos(PI / i), f * sin(PI / i));
for(register int j = 2; j < i; j++) omega[j] = omega[j - 1] * omega[1];
for(register int j = 0; j < k; j += i << 1){  // 枚举每一组
Complex *wl = a + j, *wr = wl + i;
for(register int k = 0; k < i; k++){
Complex t = omega[k] * wr[k];
wr[k] = wl[k] - t;
wl[k] = wl[k] + t;
}
}
}
if(f == -1) for(register int i = 0; i < k; i++) a[i].r /= k;
}

int main(){
n = getint(), m = getint();
for(register int i = 0; i <= n; i++) a[i].r = getint();
for(register int i = 0; i <= m; i++) b[i].r = getint();
n += m;
for(k = 1; k <= n; k <<= 1);
FFT(a, 1), FFT(b, 1);
for(register int i = 0; i < k; i++) a[i] = a[i] * b[i];
FFT(a, -1);
for(register int i = 0; i < n; i++) printf("%d ", int(a[i].r + 0.5));
printf("%d\n", int(a[n].r + 0.5));
return 0;
}
```

评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai