Luogu P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

代码中的变量 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
int inv2 = inv(2);
inline void Or(int &x, int &y) {
    y = addmod(y + x);
}
inline void OrInv(int &x, int &y) {
    y = redmod(y - x);
}
inline void And(int &x, int &y) {
    x = addmod(x + y);
}
inline void AndInv(int &x, int &y) {
    x = redmod(x - y);
}
inline void Xor(int &x, int &y) {
    int u = x, v = y;
    x = addmod(u + v);
    y = redmod(u - v);
}
inline void XorInv(int &x, int &y) {
    int u = x, v = y;
    x = addmod(u + v) * inv2 % MOD;
    y = redmod(u - v) * inv2 % MOD;
}
void FMTFWT(int n, int *a, void (*oper)(int &, int &)) {
    for (int len = 2, halflen = 1; len <= n; len <<= 1, halflen <<= 1) {
        for (int l = 0, r = len - 1; r < n; l += len, r += len) {
            for (int i = l, j = l + halflen; j <= r; ++i, ++j) {
                oper(a[i], a[j]);
            }
        }
    }
}