异或在算法竞赛中的应用#

注：本文部分内容由AI润色排版

异或，英文为 Exclusive OR，通常简写为 XOR。在 C++ 中，异或运算符写作 ^。

对于刚接触算法竞赛的选手来说，异或题经常给人一种“技巧性很强”的感觉：有些题只需要把所有数字异或一遍，有些题却需要使用 01 Trie、可持久化数据结构，甚至线性基和快速沃尔什变换。

这些题目看似相差很远，实际上可以归纳为三类基本思想：

抵消性：相同数字异或两次会消失；
按位决策：异或值的大小首先取决于最高不同位；
线性结构：异或可以看作二元域上的向量加法。

一、异或的基本性质#

1. 单个位上的异或#

对于两个二进制位，异或运算规则如下：

$a$	$b$	$a\oplus b$
0	0	0
0	1	1
1	0	1
1	1	0

也就是说：

两个二进制位相同时结果为 $0$ ，不同时结果为 $1$ 。

例如：

1
  101101
2
^ 011001
3
--------
4
  110100

在 C++ 中可以写成：

1
int c = a ^ b;

2. 基本代数性质#

异或满足以下性质：

a\oplus 0=a

a\oplus a=0

a\oplus b=b\oplus a

(a\oplus b)\oplus c=a\oplus(b\oplus c)

由此可以得到：

a\oplus b\oplus b=a

这意味着异或的逆运算仍然是异或。

若：

a\oplus b=c

那么：

a\oplus c=b

以及：

b\oplus c=a

因此，在处理异或等式时，也可以进行类似“移项”的操作，只不过移项后使用的仍然是异或。

3. 相同元素的抵消#

考虑下面的序列：

1
3, 5, 3, 7, 5

将所有数字异或：

3\oplus5\oplus3\oplus7\oplus5

利用交换律和结合律重新排列：

(3\oplus3)\oplus(5\oplus5)\oplus7

相同数字两两抵消：

0\oplus0\oplus7=7

因此，如果一个数组中只有一个数字出现奇数次，其余数字都出现偶数次，那么将所有元素异或起来，就能得到那个特殊数字。

1
int answer = 0;
2

3
for (int x : a) {
4
    answer ^= x;
5
}

时间复杂度为 $O(n)$ ，额外空间复杂度为 $O(1)$ 。

参考与练习

OI Wiki：位操作

洛谷 P1469 找筷子：利用相同元素的抵消性质寻找未配对元素。

Codeforces 276D — Little Girl and Maximum XOR：从最高不同位分析区间中的最大异或值。

二、异或方程与计数#

考虑下面的问题：

给定一个数组 $a$ 和整数 $k$ ，统计有多少对下标 $i<j$ ，满足
$a_i\oplus a_j=k$

利用异或移项：

a_i\oplus a_j=k

两边同时异或 $a_j$ ，得到：

a_i=a_j\oplus k

因此，当我们扫描到 $a_j$ 时，只需要查询此前出现过多少个：

a_j\oplus k

可以使用哈希表记录每个数字已经出现的次数：

1
long long countPairs(const vector<int>& a, int k) {
2
    unordered_map<int, long long> count;
3
    long long answer = 0;
4

5
    for (int x : a) {
6
        answer += count[x ^ k];
7
        ++count[x];
8
    }
9

10
    return answer;
11
}

这里必须先查询，再插入当前元素。

因为哈希表中只应保存当前位置之前的元素，这样才能保证统计的是满足 $i<j$ 的数对。

这种问题可以总结为：

当题目给出了两个数的异或结果，并要求寻找另一个数时，可以优先尝试使用异或移项。

参考与练习

Codeforces 742B — Arpa’s obvious problem and Mehrdad’s terrible solution：异或方程与数对计数的经典应用。

三、前缀异或#

1. 区间异或#

定义前缀异或：

pre_i=a_1\oplus a_2\oplus\cdots\oplus a_i

并令：

pre_0=0

那么区间 $[l,r]$ 的异或值为：

a_l\oplus a_{l+1}\oplus\cdots\oplus a_r =pre_r\oplus pre_{l-1}

展开右侧：

pre_r\oplus pre_{l-1}

(a_1\oplus\cdots\oplus a_{l-1}\oplus a_l\oplus\cdots\oplus a_r) \oplus (a_1\oplus\cdots\oplus a_{l-1})

前面的公共部分各出现两次，全部抵消，最终只剩下：

a_l\oplus a_{l+1}\oplus\cdots\oplus a_r

代码与前缀和非常相似：

1
vector<int> prefixXor(n + 1, 0);
2

3
for (int i = 1; i <= n; ++i) {
4
    prefixXor[i] = prefixXor[i - 1] ^ a[i];
5
}
6

7
int rangeXor = prefixXor[r] ^ prefixXor[l - 1];

2. 统计异或值为 $k$ 的子数组#

现在希望统计满足：

a_l\oplus a_{l+1}\oplus\cdots\oplus a_r=k

的区间数量。

利用前缀异或：

pre_r\oplus pre_{l-1}=k

移项可得：

pre_{l-1}=pre_r\oplus k

因此，在扫描到当前前缀异或值 $pre_r$ 时，只需要统计此前出现过多少次：

pre_r\oplus k

1
long long countSubarraysXorK(const vector<int>& a, int k) {
2
    unordered_map<int, long long> count;
3

4
    // 空前缀 pre[0] = 0
5
    count[0] = 1;
6

7
    int prefix = 0;
8
    long long answer = 0;
9

10
    for (int x : a) {
11
        prefix ^= x;
12

13
        answer += count[prefix ^ k];
14
        ++count[prefix];
15
    }
16

17
    return answer;
18
}

初始化：

1
count[0] = 1;

表示空前缀。

如果从数组开头到当前位置的异或值本身等于 $k$ ，那么：

prefix\oplus k=0

此时空前缀应当作为一个合法选择被统计。

3. 树上的路径异或#

下面讨论的是无向带权树，路径的权值定义为路径上所有边权的异或值。

任选一个节点作为根，定义：

dis_u

表示根节点到节点 $u$ 的路径异或值。

如果边 $(u,v)$ 的权值为 $w$ ，那么在 DFS 过程中：

1
dis[v] = dis[u] ^ w;

对于任意两个节点 $u,v$ ，它们之间路径的异或值为：

path(u,v)=dis_u\oplus dis_v

原因是根到 $u$ 与根到 $v$ 的公共部分会出现两次，从而相互抵消。

这和数组中的：

pre_r\oplus pre_{l-1}

本质上是同一种结构。

参考与练习

OI Wiki：位操作

洛谷 P2420 让我们异或吧：无向带权树上的路径异或查询。

四、01 Trie 与异或极值#

1. 最大异或问题#

考虑经典问题：

给定若干非负整数，对于一个查询值 $x$ ，寻找集合中的一个数 $y$ ，使得 $x\oplus y$ 最大。

整数的大小首先由二进制表示中的最高不同位决定，因此应从最高位向最低位考虑。

假设 $x$ 当前位为 $0$ ：

如果 $y$ 当前位为 $1$ ，这一位的异或结果为 $1$ ；
如果 $y$ 当前位为 $0$ ，这一位的异或结果为 $0$ 。

为了使最终答案尽可能大，应优先选择当前位与 $x$ 不同的数字。

可以把所有数字的二进制表示插入一棵 Trie：

每一层对应一个二进制位；
child[0] 表示这一位是 $0$ ；
child[1] 表示这一位是 $1$ ；
查询时优先进入与 $x$ 当前位相反的分支。

2. 基础模板#

下面的模板假设输入为不超过 $2^{31}-1$ 的非负整数，因此处理第 $30$ 位到第 $0$ 位。

实际使用时，应根据题目数据范围调整最高位。

1
struct BinaryTrie {
2
    static constexpr int MAX_BIT = 30;
3

4
    struct Node {
5
        int child[2] = {-1, -1};
6
        int count = 0;
7
    };
8

9
    vector<Node> trie;
10

11
    BinaryTrie() {
12
        trie.emplace_back();
13
    }
14

15
    bool empty() const {
16
        return trie[0].count == 0;
17
    }
18

19
    void insert(int x) {
20
        int node = 0;
21
        ++trie[node].count;
22

23
        for (int bit = MAX_BIT; bit >= 0; --bit) {
24
            int value = (x >> bit) & 1;
25

26
            if (trie[node].child[value] == -1) {
27
                trie[node].child[value] =
28
                    static_cast<int>(trie.size());
29
                trie.emplace_back();
30
            }
31

32
            node = trie[node].child[value];
33
            ++trie[node].count;
34
        }
35
    }
36

37
    int queryMaxXor(int x) const {
38
        // 调用前必须保证 Trie 非空
39
        int node = 0;
40
        int answer = 0;
41

42
        for (int bit = MAX_BIT; bit >= 0; --bit) {
43
            int value = (x >> bit) & 1;
44
            int preferred = value ^ 1;
45

46
            int preferredChild = trie[node].child[preferred];
47

48
            if (preferredChild != -1 &&
49
                trie[preferredChild].count > 0) {
50
                answer |= 1 << bit;
51
                node = preferredChild;
52
            } else {
53
                int fallbackChild = trie[node].child[value];
54
                node = fallbackChild;
55
            }
56
        }
57

58
        return answer;
59
    }
60
};

每次插入或查询都会经过固定数量的二进制位，因此复杂度为：

O(B)

其中 $B$ 是处理的二进制位数。

处理前缀异或问题时，通常需要在开始查询前先插入前缀异或值 $0$ 。

3. 动态插入与删除#

如果题目要求支持删除，不能直接删除 Trie 节点，因为同一个前缀可能被多个数字共享。

正确做法是在每个节点维护经过该节点的数字数量。

1
void add(int x, int delta) {
2
    int node = 0;
3
    trie[node].count += delta;
4

5
    for (int bit = MAX_BIT; bit >= 0; --bit) {
6
        int value = (x >> bit) & 1;
7

8
        if (trie[node].child[value] == -1) {
9
            trie[node].child[value] =
10
                static_cast<int>(trie.size());
11
            trie.emplace_back();
12
        }
13

14
        node = trie[node].child[value];
15
        trie[node].count += delta;
16
    }
17
}

其中：

delta = 1 表示插入；
delta = -1 表示删除。

执行删除操作时，必须保证集合中至少存在一个对应的数字。如果题目不保证这一点，还需要额外维护每个完整数字的出现次数。

4. 最大异或与最小异或#

求最大异或时，应优先选择相反位：

1
preferred = bit ^ 1

求最小异或时，应优先选择相同位：

1
preferred = bit

两种操作的本质相同，区别只在于每一层优先选择哪个分支。

参考与练习

OI Wiki：字典树 Trie

洛谷 P4551 最长异或路径：树上前缀异或与最大异或查询。

Codeforces 706D — Vasiliy’s Multiset：动态插入、删除与最大异或查询。

Codeforces 923C — Perfect Security：可删除多重集合中的最小异或匹配。

五、Trie 上统计 $x\oplus y<k$ #

最大异或查询只需要决定当前位应优先选择相同还是不同。

但有些题目要求统计：

x\oplus y<k

此时需要同时考虑 $x$ 、 $y$ 和 $k$ 的当前位。

令：

z=x\oplus y

问题转化为在 Trie 中统计满足：

z<k

的 $y$ 的数量。

仍然从最高位向最低位处理。

1. 当 $k$ 当前位为 $0$ #

如果此前各位仍然与 $k$ 相等，那么为了保证结果不超过 $k$ ， $z$ 当前位只能为 $0$ 。

因此， $y$ 当前位必须与 $x$ 当前位相同，并继续向低位判断。

2. 当 $k$ 当前位为 $1$ #

此时有两种选择。

如果令 $z$ 当前位为 $0$ ，那么答案在这一位已经严格小于 $k$ ，后续所有位都可以任意选择。因此，可以直接加入对应子树中的所有元素数量。

如果令 $z$ 当前位为 $1$ ，当前前缀仍然与 $k$ 相等，需要继续向低位判断。

1
long long countLess(int x, int k) const {
2
    int node = 0;
3
    long long answer = 0;
4

5
    for (int bit = MAX_BIT; bit >= 0; --bit) {
6
        if (node == -1) {
7
            break;
8
        }
9

10
        int xb = (x >> bit) & 1;
11
        int kb = (k >> bit) & 1;
12

13
        if (kb == 1) {
14
            // 令 xor 当前位为 0，此后一定小于 k
15
            int same = trie[node].child[xb];
16

17
            if (same != -1) {
18
                answer += trie[same].count;
19
            }
20

21
            // 令 xor 当前位为 1，继续保持前缀相等
22
            node = trie[node].child[xb ^ 1];
23
        } else {
24
            // xor 当前位只能为 0
25
            node = trie[node].child[xb];
26
        }
27
    }
28

29
    return answer;
30
}

如果题目要求统计：

x\oplus y\geq k

可以先计算集合中的元素总数，再减去满足：

x\oplus y<k

的元素数量。

参考与练习

OI Wiki：字典树 Trie

Codeforces 817E — Choosing The Commander：动态集合中的异或上界统计。

Codeforces 665E — Beautiful Subarrays：前缀异或与 Trie 统计的结合。

六、可持久化 01 Trie#

1. 普通 Trie 的局限#

普通 Trie 可以回答：

在当前集合中，哪个数字与 $x$ 的异或值最大？

但是，如果查询变为：

只允许选择编号位于 $[l,r]$ 中的元素。

普通 Trie 就无法直接判断某个分支中是否存在编号属于目标区间的元素。

一种常见解决方法是：为每个前缀建立一个 Trie 版本。

2. 可持久化的基本思想#

假设已经有表示前 $i-1$ 个元素的 Trie。

插入第 $i$ 个元素时：

不复制整棵 Trie；
只复制从根节点到该数字叶节点的路径；
没有变化的子树继续与旧版本共享。

如果每个数字有 $B$ 个二进制位，那么每次插入只会新增：

O(B)

个节点。

因此，插入 $n$ 个数字的总空间复杂度约为：

O(nB)

3. 区间查询与版本作差#

设：

root[r] 表示插入前 $r$ 个元素后的 Trie；
root[l - 1] 表示插入前 $l-1$ 个元素后的 Trie。

某个节点在编号区间 $[l,r]$ 中的元素数量，可以通过两个版本的节点计数相减得到：

count(root_r)-count(root_{l-1})

查询最大异或时，仍然优先尝试相反位，但只有当该分支在两个版本之间的数量差大于零时，才能进入该分支。

这一思想与主席树查询区间信息时的“版本作差”非常相似。

4. P4735 中的前缀异或转化#

设序列的前缀异或为：

s_i=a_1\oplus a_2\oplus\cdots\oplus a_i

并令：

s_0=0

如果需要在 $p\in[l,r]$ 中选择一个位置，最大化：

x\oplus a_p\oplus a_{p+1}\oplus\cdots\oplus a_n

那么：

a_p\oplus a_{p+1}\oplus\cdots\oplus a_n =s_n\oplus s_{p-1}

原式变为：

x\oplus s_n\oplus s_{p-1}

其中：

x\oplus s_n

在当前查询中是固定值。

因此，问题变成：

在前缀编号 $p-1\in[l-1,r-1]$ 中选择一个 $s_{p-1}$ ，使它与固定值 $x\oplus s_n$ 的异或最大。

这正是带编号区间限制的最大异或查询，因此可以使用可持久化 01 Trie。

参考与练习

OI Wiki：可持久化字典树

洛谷 P4735 最大异或和：动态添加元素与带编号范围的最大异或查询。

七、异或线性基#

01 Trie 通常解决的是：

从集合中选择一个数，与给定值进行异或。

线性基解决的则是：

从集合中选择任意多个数，它们能够异或出哪些结果？

这是两类不同的问题。

1. 将整数看作向量#

一个二进制整数可以看作由 $0$ 和 $1$ 构成的向量。

例如：

异或相当于每一位在模 $2$ 意义下相加：

因此，异或可以看作二元域 $\mathrm{GF}(2)$ 上的向量加法。

线性基就是从原集合中选出一组线性无关向量，使原集合能够异或得到的所有结果，都可以由这组基向量表示。

2. 插入一个数字#

维护：

1
basis[bit]

表示一个最高有效位为 bit 的基向量。

插入 $x$ 时，从最高位向最低位检查。

如果 $x$ 的第 bit 位为 $0$ ，无需处理。

如果该位为 $1$ ：

如果 basis[bit] 为空，就把 $x$ 放入该位置；
否则令 $x$ 异或 basis[bit]，消去当前最高位。

下面的代码假设输入不超过 $10^{18}$ ，因此处理第 $60$ 位到第 $0$ 位。

1
#include <cstdint>
2

3
using u64 = std::uint64_t;
4

5
struct LinearBasis {
6
    static constexpr int MAX_BIT = 60;
7

8
    u64 basis[MAX_BIT + 1]{};
9

10
    bool insert(u64 x) {
11
        for (int bit = MAX_BIT; bit >= 0; --bit) {
12
            if (((x >> bit) & 1ULL) == 0) {
13
                continue;
14
            }
15

16
            if (basis[bit] == 0) {
17
                basis[bit] = x;
18
                return true;
19
            }
20

21
            x ^= basis[bit];
22
        }
23

24
        return false;
25
    }
26
};

如果最终 $x=0$ ，说明原来的 $x$ 可以由已有基向量异或得到，因此它与已有向量线性相关。

3. 最大子集异或#

从最高位向最低位尝试使用每个基向量：

1
u64 getMax() const {
2
    u64 answer = 0;
3

4
    for (int bit = MAX_BIT; bit >= 0; --bit) {
5
        answer = max(answer, answer ^ basis[bit]);
6
    }
7

8
    return answer;
9
}

这里仍然是在进行最高位贪心。

如果：

1
answer ^ basis[bit] > answer

说明加入该基向量后，答案在某个关键高位上变大，因此应保留这次变化。

4. 秩与方案数量#

假设原集合共有 $n$ 个数字，将它们视为 $\mathrm{GF}(2)$ 上的向量，其秩为 $r$ 。

那么线性张成空间中一共有：

2^r

个不同的异或结果。

从所有 $2^n$ 个子集中选择一个子集，相当于从 $\mathrm{GF}(2)^n$ 中选择一组系数。

从系数空间到异或结果空间的线性映射，其核的维数为：

n-r

因此，对于任意一个可以被表示的目标异或值，恰好有：

2^{n-r}

个子集能够得到该值，其中包括空集。

如果目标值不在线性张成空间中，则方案数为零。

参考与练习

OI Wiki：线性基

洛谷 P3812【模板】线性基：最大子集异或。

洛谷 P3857 彩灯：利用线性基的秩计算可达到状态数量。

洛谷 P4570 元素：带权选择与线性无关性。

Codeforces 959F — Mahmoud and Ehab and yet another xor task：可表示性、秩与方案数。

八、图上的异或与环空间#

下面讨论的是无向带权图。起点与终点需要位于同一个连通分量中，路径权值定义为经过边权的异或值。

1. 树上的情况#

在树上，两个节点之间的路径唯一。

定义根节点到 $u$ 的树上路径异或值为 $dis_u$ ，那么：

path(u,v)=dis_u\oplus dis_v

只需要一次 DFS 就能计算所有 $dis$ 。

2. 一般图中的环#

在一般图中，两个节点之间可能存在多条不同路径。

先任选一棵 DFS 生成树，并计算：

dis_u

表示根节点到 $u$ 的树上路径异或值。

对于一条连接 $u,v$ 、边权为 $w$ 的非树边，它与生成树中的路径共同构成一个环，其异或值为：

cycle=dis_u\oplus dis_v\oplus w

其中：

$dis_u$ 表示根到 $u$ 的树上路径；
$w$ 表示边 $(u,v)$ ；
$dis_v$ 表示根到 $v$ 的树上路径。

这三部分共同组成一个闭合结构。

3. 环空间与路径调整#

假设已经得到一条从起点 $s$ 到终点 $t$ 的基础路径，其异或值为：

d=dis_s\oplus dis_t

图中的其他可行路线与这条基础路线之间的差异，可以由若干个环的异或组合产生。

因此，其他路径的异或值可以表示为：

d\oplus c_1\oplus c_2\oplus\cdots

其中每个 $c_i$ 都来自图中的环空间。

将所有环异或值插入线性基之后，就可以使用线性基最大化或最小化基础路径异或值。

1
u64 maximize(u64 x) const {
2
    for (int bit = MAX_BIT; bit >= 0; --bit) {
3
        x = max(x, x ^ basis[bit]);
4
    }
5

6
    return x;
7
}

参考与练习

OI Wiki：线性基

洛谷 P4151 最大 XOR 和路径：生成树、环异或与线性基。

Codeforces 845G — Shortest Path Problem?：使用环空间处理最小异或路径。

Codeforces 724G — Xor-matic Number of the Graph：环空间、线性基与按位贡献统计。

九、扩展：带位置的前缀线性基#

普通线性基维护的是整个集合。

如果题目要求回答：

在区间 $[l,r]$ 中任选若干个数，求最大子集异或。

就需要限制基向量所使用元素的位置。

一种经典方法是给每个基向量附加一个时间戳：

1
basis[bit]：基向量的值
2
position[bit]：该基向量保留的最新位置

插入位于位置 $pos$ 的新元素时，从高位向低位消元。

如果新元素的位置比当前基向量记录的位置更靠后，就交换：

1
当前向量 x、当前时间戳 pos

与：

1
basis[bit]、position[bit]

这样可以在保持线性张成空间不变的前提下，让线性基尽量保留出现位置更靠后的向量。

查询区间左端点为 $l$ 时，只使用满足：

position[bit]\geq l

的基向量。

需要注意的是，被换出的旧向量不能直接丢弃。它仍然可能包含低位上的有效信息，因此必须继续向更低位进行消元。

这一结构常被称为前缀线性基或带位置线性基，适合处理离线区间最大子集异或问题。

参考与练习

OI Wiki：线性基

Codeforces 1100F — Ivan and Burgers：区间最大子集异或。

洛谷 P3292 幸运数字：树上路径与线性基合并。

十、Nim 游戏与异或和#

1. 游戏规则#

经典 Nim 游戏有若干堆石子。

两名玩家轮流操作，每次可以：

选择任意一堆；
从中取走任意多个石子；
但至少取走一个。

无法继续操作的玩家失败。

设各堆石子数量为：

a_1,a_2,\ldots,a_n

定义 Nim 和：

S=a_1\oplus a_2\oplus\cdots\oplus a_n

结论为：

如果 $S=0$ ，当前玩家必败；
如果 $S\neq0$ ，当前玩家必胜。

2. 为什么 $S=0$ 是必败状态#

假设当前 Nim 和为零。

玩家将某一堆 $a_i$ 修改为 $b_i$ ，且：

a_i\neq b_i

新的异或和为：

0\oplus a_i\oplus b_i =a_i\oplus b_i

由于：

a_i\neq b_i

因此：

a_i\oplus b_i\neq0

所以，从异或和为零的状态出发，无论如何操作，都会进入异或和非零的状态。

3. 为什么 $S\neq0$ 时可以变成零#

设 $S$ 的最高有效位为第 $k$ 位。

因为 $S$ 的第 $k$ 位是 $1$ ，所以至少存在一堆 $a_i$ ，其第 $k$ 位也是 $1$ 。

令：

b_i=a_i\oplus S

由于 $S$ 的最高有效位会把 $a_i$ 的第 $k$ 位从 $1$ 变成 $0$ ，因此：

b_i<a_i

这是一次合法的减少操作。

操作后的 Nim 和为：

S\oplus a_i\oplus b_i

代入：

b_i=a_i\oplus S

得到：

S\oplus a_i\oplus a_i\oplus S=0

因此，异或和非零的玩家总能一步进入异或和为零的状态。

参考与练习

OI Wiki：公平组合游戏

洛谷 P2197【模板】Nim 游戏：标准 Nim 游戏胜负判断。

Codeforces 1383B — GameGame：从最高有效位分析异或博弈。

十一、扩展：XOR-FWT 与异或卷积#

1. XOR 卷积#

给定两个长度为 $n$ 的数组 $A,B$ ，定义：

C_k=\sum_{i\oplus j=k}A_iB_j

这称为 XOR 卷积。

直接枚举所有 $i,j$ 的时间复杂度为：

O(n^2)

当数组长度是 $2$ 的幂时，可以使用快速沃尔什变换，将复杂度优化为：

O(n\log n)

2. XOR 蝶形#

对于一对数 $x,y$ ，XOR-FWT 的蝶形变换为：

(x,y)\longrightarrow(x+y,x-y)

完整模板如下：

1
void fwtXor(vector<long long>& a, bool inverse) {
2
    const int n = static_cast<int>(a.size());
3

4
    for (int len = 1; len < n; len <<= 1) {
5
        for (int start = 0; start < n; start += len << 1) {
6
            for (int i = 0; i < len; ++i) {
7
                const long long x = a[start + i];
8
                const long long y = a[start + i + len];
9

10
                a[start + i] = x + y;
11
                a[start + i + len] = x - y;
12
            }
13
        }
14
    }
15

16
    if (inverse) {
17
        for (long long& x : a) {
18
            x /= n;
19
        }
20
    }
21
}

卷积过程可以写成：

1
fwtXor(a, false);
2
fwtXor(b, false);
3

4
for (int i = 0; i < n; ++i) {
5
    a[i] *= b[i];
6
}
7

8
fwtXor(a, true);

最终数组 a 就是 XOR 卷积结果。

对 XOR-FWT 连续执行两次变换，会使每个元素整体乘以 $n$ ，因此逆变换需要除以 $n$ 。

在普通整数运算中，应确保最终结果能够整除 $n$ ，并注意中间值可能超过 long long 的范围。

在模意义下，不能直接使用整数除法，而应乘以：

n^{-1}\pmod M

其中 $n^{-1}$ 是 $n$ 关于模数 $M$ 的乘法逆元。

参考资料

OI Wiki：快速沃尔什变换

我的博客

异或在算法竞赛中的应用#

一、异或的基本性质#

1. 单个位上的异或#

2. 基本代数性质#

3. 相同元素的抵消#

二、异或方程与计数#

三、前缀异或#

1. 区间异或#

2. 统计异或值为 kkk 的子数组#

3. 树上的路径异或#

四、01 Trie 与异或极值#

1. 最大异或问题#

2. 基础模板#

3. 动态插入与删除#

4. 最大异或与最小异或#

五、Trie 上统计 x⊕y<kx\oplus y<kx⊕y<k#

1. 当 kkk 当前位为 000#

2. 当 kkk 当前位为 111#

六、可持久化 01 Trie#

1. 普通 Trie 的局限#

2. 可持久化的基本思想#

3. 区间查询与版本作差#

4. P4735 中的前缀异或转化#

七、异或线性基#

1. 将整数看作向量#

2. 插入一个数字#

3. 最大子集异或#

4. 秩与方案数量#

八、图上的异或与环空间#

1. 树上的情况#

2. 一般图中的环#

3. 环空间与路径调整#

九、扩展：带位置的前缀线性基#

十、Nim 游戏与异或和#

1. 游戏规则#

2. 为什么 S=0S=0S=0 是必败状态#

3. 为什么 S≠0S\neq0S=0 时可以变成零#

十一、扩展：XOR-FWT 与异或卷积#

1. XOR 卷积#

2. XOR 蝶形#

分享文章

换条路线

2. 统计异或值为 $k$ 的子数组#

五、Trie 上统计 $x\oplus y<k$ #

1. 当 $k$ 当前位为 $0$ #

2. 当 $k$ 当前位为 $1$ #

2. 为什么 $S=0$ 是必败状态#

3. 为什么 $S\neq0$ 时可以变成零#