问题导入
给定一个图。求一条回路使得该路径的异或和最大。
线性基
线性基的构造
对于一个数集 \(S\)，我们可以用以下代码构造一组线性基 \(D\)。
for(int i = 1; i <= cnt; ++i) {
LL cur = S[i];
for(int k = 59; k >= 0; --k) {
if(cur & (1ll << k)) {
if(d[k]) cur ^= d[k];
else {
d[k] = cur;
break;
}
}
}
}
线性基的性质及略证
如此构建后，线性基中的所有数满足如下性质。
-
若 \(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\) 中的数异或表示。这与性质 3 矛盾。假设不成立，性质 4 成立。
解最大异或和
由于性质 0，我们可以直接贪心地找最大异或和。
从高位往低位扫描，时刻记录一个 ans。若 ans 的第 \(i\) 位为 \(0\)，则异或上一个 \(d_i\)。否则不异或 \(d_i\)。
你可能会觉得——这样最大异或和不总是 11111…11 吗？事实上，不是所有的 \(d_i\) 都非零哦。
引入问题的解
随便找一棵 dfs 树，通过返祖边或者横插边构成若干个基本环。可以证明，所有的环均可以由基本环异或表示。
将基本环的异或和丢进线性基，找最大异或和即可。
原文地址：http://www.cnblogs.com/sqrtyz/p/16814954.html
