Luogu P3803 【模板】多项式乘法（FFT）

需要注意的是，题目中要开几十万个 Complex，而且和矩阵乘法不同的是代码中没有开非全局变量的 Complex 的需求，所以可以不用写构造函数，节省一些运行时间。

代码中的变量 n 的意义是多项式的长度，也就是度数加一，而非度数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const double twoPI = acos(-1) * 2;

struct Complex {
    double x, y;
    inline Complex operator+(const Complex sec) const {
        return Complex{x: x + sec.x, y: y + sec.y};
    }
    inline Complex operator-(const Complex sec) const {
        return Complex{x: x - sec.x, y: y - sec.y};
    }
    inline Complex operator*(const Complex sec) const {
        return Complex{x: x * sec.x - y * sec.y, y: x * sec.y + y * sec.x};
    }
};
Complex Zero = Complex{x: 0, y: 0},
        One = Complex{x: 1, y: 0};

int swp[MAXN + 10];
void EvaSwp(int n) {
    int mxdeg = n >> 1;
    for (int i = 1; i < n; ++i) {
        swp[i] = (swp[i >> 1] >> 1) + ((i & 1) ? mxdeg : 0);
    }
}
void Swp(int n, Complex *a) {
    for (int i = 0; i < n; ++i) {
        if (swp[i] > i) {
            swap(a[i], a[swp[i]]);
        }
    }
}
void FFT(int n, Complex *a, int getinv) {
    Swp(n, a);
    for (int len = 2, halflen = 1; len <= n; len <<= 1, halflen <<= 1) {
        Complex wlen = Complex{x: cos(twoPI / len), y: sin(twoPI / len)};
        for (int l = 0, r = len - 1; r < n; l += len, r += len) {
            Complex w = One;
            for (int i = l, j = l + halflen; j <= r; ++i, ++j, w = w * wlen) {
                Complex u = a[i],
                        v = a[j] * w;
                a[i] = u + v;
                a[j] = u - v;
            }
        }
    }
    if (getinv == -1) {
        reverse(a + 1, a + n);
        for (int i = 0; i < n; ++i) {
            a[i].x /= n;
        }
    }
}