Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

FWT 模板

发表于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟
标签：        

用于快速求位运算卷积。

AND和OR的变换和FMT是等价的。

XOR的变换有

$$
FWT(a) _ i = \sum _ {j = 0} ^ {2 ^ n - 1} (-1) ^ {|i \wedge j|} a _ j
$$

可以证明，如果有 $c _ i = \sum _ {j \oplus k = i} a _ j b _ k$ ，那么有 $FWT(c) = FWT(a)FWT(b)$ 。

查看代码 
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 998244353, inv2 = 499122177;
void add(int &x, int k)
{
    x += k;
    (x > mod) && (x -= mod);
    (x < -mod) && (x += mod);
}
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        (c == '-') && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    (flag) && (x = ~x + 1);
}
const int N = 17, M = 1 << N;
int bit, tot;
void fwt_or(int *x, int op)
{
    for (int mid = 1; mid < tot; mid <<= 1)
        for (int i = 0; i < tot; i += mid << 1)
            for (int j = 0; j < mid; j++)
                add(x[i | j | mid], x[i | j] * op);
    for (int i = 0; i < tot; i++)
        add(x[i], mod);
}
void fwt_and(int *x, int op)
{
    for (int mid = 1; mid < tot; mid <<= 1)
        for (int i = 0; i < tot; i += mid << 1)
            for (int j = 0; j < mid; j++)
                add(x[i | j], x[i | j | mid] * op);
    for (int i = 0; i < tot; i++)
        add(x[i], mod);
}
void fwt_xor(int *x, int op)
{
    for (int mid = 1; mid < tot; mid <<= 1)
        for (int i = 0; i < tot; i += mid << 1)
            for (int j = 0; j < mid; j++)
            {
                LL p = x[i | j], q = x[i | j | mid];
                x[i | j] = (LL)(p + q) * op % mod, x[i | j | mid] = (LL)(p - q) * op % mod;
            }
    for (int i = 0; i < tot; i++)
        add(x[i], mod);
}
int main()
{
    read(bit);
    tot = 1 << bit;
    static int a[M], b[M], c[M], d[M];
    for (int i = 0; i < tot; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < tot; i++)
        scanf("%d", &b[i]);

    for (int i = 0; i < tot; i++)
        c[i] = a[i];
    for (int i = 0; i < tot; i++)
        d[i] = b[i];
    fwt_or(c, 1), fwt_or(d, 1);
    for (int i = 0; i < tot; i++)
        c[i] = (LL)c[i] * d[i] % mod;
    fwt_or(c, -1);
    for (int i = 0; i < tot; i++)
        printf("%d ", c[i]);
    puts("");

    for (int i = 0; i < tot; i++)
        c[i] = a[i];
    for (int i = 0; i < tot; i++)
        d[i] = b[i];
    fwt_and(c, 1), fwt_and(d, 1);
    for (int i = 0; i < tot; i++)
        c[i] = (LL)c[i] * d[i] % mod;
    fwt_and(c, -1);
    for (int i = 0; i < tot; i++)
        printf("%d ", c[i]);
    puts("");

    for (int i = 0; i < tot; i++)
        c[i] = a[i];
    for (int i = 0; i < tot; i++)
        d[i] = b[i];
    fwt_xor(c, 1), fwt_xor(d, 1);
    for (int i = 0; i < tot; i++)
        c[i] = (LL)c[i] * d[i] % mod;
    fwt_xor(c, inv2);
    for (int i = 0; i < tot; i++)
        printf("%d ", c[i]);
    puts("");

    return 0;
}
相关文章