【算法竞赛】线性基
问题导入
给定一个图。求一条回路使得该路径的异或和最大。
线性基
线性基的构造
对于一个数集 $S$，我们可以用以下代码构造一组线性基 $D$。
1for(int i = 1; i <= cnt; ++i) {
2 LL cur = S[i];
3 for(int k = 59; k >= 0; --k) {
4 if(cur & (1ll << k)) {
5 if(d[k]) cur ^= d[k];
6 else {
7 d[k] = cur;
8 break;
9 }
10 }
11 }
12 }
线性基的性质及略证
如此构建后，线性基中的所有数满足如下性质。
若 $d_i$ 非零：$d_i$ 在第 $i$ 位是 $1$，这也是它的最高位。这也意味着：对于所有比它小的 $d_j$，其第 $i$ 位必为零。 若 $d_i$ 为零：………… 那它就是零呗。
数集 $S$ 中的任意数将可以被 $D$ 中的若干数唯一异或表示。
$D$ 中的任意数将可以被 $S$ 中的若干数异或表示。
选择 $D$ 中的若干数进行异或和，结果不可能为 $0$。
不存在一个长度更小的数集 $D$，满足上述性质。
性质 1 的证明提示：由上述代码可见，一个数要么在经过若干次异或后进入线性基，要么经过若干次异或后变为 $0$。“唯一”可由性质 3 推导而来。
性质 2 的证明提示：考虑数学归纳。线性基中最大的数一定属于 $S$；次大的数要么属于 $S$，要么由某个属于 $S$ 中的数和最大的数经过一次异或后得来……
性质 3 的证明提示：选择出的数一定有一个最大的数。这个最大的数的最高二进制位可以证明只有它自己为 $1$，其他的选择出的数该位全为 $0$。
性质 4 的证明提示：考虑削减一个 $D$ 中的数 $x$。假设 $x$ 由 $S$ 中的数 $v$ 经过若干次异或插入进线性基，这意味着 $v$ 可以由 包括 $x$ 在内的 若干 $D$ 中的数异或表示。若存在一个长度更小的数集 $D$，满足上述性质，那么意味着 $v$ 可以由 不包括 $x$ 在内的 若干 $D$ 中的数异或表示。这与性质 1 矛盾。假设不成立，性质 4 成立。
解最大异或和
由于性质 0，我们可以直接贪心地找最大异或和。
从高位往低位扫描，时刻记录一个 ans。若 ans 的第 $i$ 位为 $0$，则异或上一个 $d_i$。否则不异或 $d_i$。
你可能会觉得——这样最大异或和不总是 11111…11 吗？事实上，不是所有的 $d_i$ 都非零哦。
引入问题的解
随便找一棵 dfs 树，通过返祖边或者横插边构成若干个基本环。可以证明，所有的环均可以由基本环异或表示。
将基本环的异或和丢进线性基，找最大异或和即可。