1. P4570 [BJWC2011] 元素

【题意简化】给定 $n(\le 10^4)$ 种矿石，已知每种矿石元素序号和价值。元素序号异或为 $0$ , 矿石的价值会相互抵消。请求出一个子集，子集内任意序号异或不为零，求子集价值和最大是多少？

【分析】有两种思路，一种采用高斯消元法求价值最大的极大不相关子集。另一种思路，所有矿石按照价值从高到低排序，然后以序号插入线性基，如果插入成功，说明之前矿石无法表出当前矿石编号，那么此矿石价值加入答案，优先将价值高的矿石插入线性基，价值低的矿石如果不能作为基，就抛弃。

2. P3857 [TJOI2008] 彩灯

【题意简化】给定 $n(\le 50)$ 盏灯 $m(\le 50)$ 个开关，已知每个开关控制灯的情况，请求出 $n$ 盏不同的状态数量，取 $2008$ 余数。

【分析】设 $a_{ij}$ 表示第 $i$ 个开关控制第 $j$ 盏灯（ $0$ 表示不控制，$1$ 表示控制）, $s_j$ 表示第 $j$ 盏灯的状态。可以得到方程组：

$\left\{\begin{matrix} a_{11} \oplus a_{21} \oplus \dots \oplus a_{m1}=s_1\\ a_{12} \oplus a_{22} \oplus \dots \oplus a_{m2}=s_2\\ \dots \\ a_{1n} \oplus a_{2n} \oplus \dots \oplus a_{mn}=s_n\end{matrix}\right.$

系数矩阵就是开关控制灯含义，矩阵的秩就是列秩，列秩代表最多不相关开关的数量，即不相关就是灯的状态无法用其他开关表出，问题转换为求列向量的极大不相关数量 $r$，答案就是 $2^r$。

矩阵的秩等于行向量的秩，也等于列向量的秩。可以用高斯消元法求矩阵的秩，也可以求基的数量，即如果插入基成功的数量就是 $r$。

3. P4301 [CQOI2013] 新Nim游戏

【题意简化】传统 Nim 游戏的规则是：给定若干堆石子（柴火），两人轮流拿石子，选择一堆至少拿一个最多全部拿走这堆石子，不能不拿，最后拿走石子的人获胜。 现在修改规则，开始前先轮流拿着若干堆石子，之后再按照传统 Nim 游戏进行，最少拿走多少石子使得先手必胜。

【分析】 传统 Nim 游戏先手必胜策略是：所有堆石子异或和不为零。 那么先手就是留下尽量多的石子，使得剩下的任意子集异或和不为零，那么先手必胜。

那么从大到小排序，能插入就留下，否则先手就拿走。

4. P4151 [WC2011] 最大XOR和路径

【题意简化】给定一个 $n(\le 50000)$ 个点 $m(\le 10^5)$ 条边的带权图 $(D_i \le 10^{18})$ ,求 $1$ 到 $n$ 路径上权异或和的最大值。（路径不一定是简单路径）

【分析】在 $dfs$ 树上，返祖边会构成环，从 1 到 n 的所有路径上，对于不经过的非树边，会走两次，异或后没有贡献，而对于不经过的环，对答案是有贡献的。那么整个连同的环都可以经过一次，选择异或最大的就是答案。

将所有环插入线性基，求最大异或和。在 dfs 树上，d[x] 表示根到 x 路径异权值或和 。对于树边 x->y , 边权 D , d[y]=d[x]^D ; 对于非树边 x->y , 构成环，环上异或和就是 d[x]^d[y]^D ，插入线性基。

ans=d[n] , 求线性基中，答案就是 与 ans 异或的最大值。

类似的题目就是 CF845G Shortest Path Problem? ，求 1 到 n 路径的最小值。

5. P3733 [HAOI2017] 八纵八横

【题意简化】给定 $n(\le 500)$ 个点 $m(\le 500)$ 条边的连通图，原始 $m$ 条边不改变，求起点到起点路径最大异或和。

$q(\le 1000)$ 次操作, 添加一条边边权 z 的边 Add x y z , 删除一条边 Cancel k , 修改一条边 Change k z , 对于每次操作求起点到起点最大异或和。

【分析】 起点到起点，路径异或和，只有环对答案有贡献。将所有环插入线性基，求最大异或和。对于加边操作，加的边都是非树边，构成环，插入线性基。

6. CF895-C. Square Subsets

【题意简化】给定 $n(\le 10^5)$ 个非零整数 $a_i(\le 70)$ , 询问存在多少个非空子集，子集所有元素之奇为平方数。

【分析】本题有状态压缩和线性基两种思路，是一道非常好的题目。

思路一：题目中特殊条件 $a_i\le 70$, $70$ 以内的质因子个数很少，只有 $19$ 个 。我们要构成平方数，只需要考虑质因子的奇偶情况，那么就可以用状态压缩表示当前所有质因子的奇偶。定义状态 f[i][s] 表示值小于等于 i ,所有质因子状态为 s 的方法数，num[i] 表示值为 i 的个数，为了方便表述令 k=num[i]。分类讨论可以得到转移方程：

• 1.值为 $i$ 的数取奇数个 取奇数个，那么当前状态 $s$ 就要被 $i$ 改变 , 所有取奇数个方案数是 $C_k^1+C_k^3+\dots =2^{(k-1)}$ 。令 $t$ 表示值 $i$ 各个质因子的状态，可以得到转态转移方程:

  $$f[i][s\oplus t]+=f[i-1][s]*2^{(k-1)}$$

• 2.值为 $i$ 的数取偶数个 取偶数个，那么当前状态不会改变，所有取偶数个方案数就是 $C_k^2+C_k^4+...=2^{(k-1)}$, 可以得到状态转移方程: $$f[i][s]+=f[i-1][s]*2^{(k-1)}$$

特殊的对 $1$ 再进行处理, 注意需要利用 01 滚动数组或者压行空间优化。

参考代码：点击

思路二：

本质上对于符合条件的子集只需要考虑其所有因子的奇偶状态，那么对于每一个数，其质因子奇偶状态状压后，可以插入线性基。

线性基内有 $cnt$ 个非零元素, 线性基外有 $n-cnt$ 个数，这 $n-cnt$ 个数可以被线性基内元素表示出来，即能构成偶数个质因子，那么其非空子集个数就是 $2^{n-cnt}-1$ 个就是答案。

参考代码：点击

这道题目的升级版，就是 P7451 [THUSC 2017] 杜老师 , 一道好题。

7. P7451 [THUSC 2017] 杜老师

【题意简化】 $T(\le 100)$ 次询问正整数区间 $[L,R](R\le 10^7)$ , 存在多少个子集，子集之积为一个平方数。

【分析】 对于 $R\le 1000$ , 可以直接利用 $bitset$ 状压表示质数奇偶状态，线性基暴力做，期望得分 $50$ 分。

对于一个整数 $n$，超过 $\sqrt{n}$ 最多只有一个。 $\sqrt{10^7}<3200$ 质数个数不超过 $450$ , 对于超过 $\sqrt{10^7}$ 的质因子利用 $map$ 处理，使用线性基，时间复杂度为 $O(n* \frac{B^2}{w})$ , $n$ 太大无法通过。

有一个重要性质，当插入线性基数比较多时，线性基被填充满了。通过打表发现当区间长度 $R-L+1$ 大于 $2*\sqrt{n}$ 线性基会被填满。 枚举每一个质数 $p$，如果 $\frac{L-1}{p}\ne\frac{R}{p}$ ，那么区间内必定出现 $p$ (但是不确定出现奇偶次)，一定会出现在线性基内，时间复杂度降低为 $O(n)$。

线性基内元素个数为 $num$ ,那么答案就是 $2^{R-L+1-num}$ ,总结一下：小区间线性基，大区间直接判断。

参考代码：点击

8.CF724G Xor-matic Number of the Graph

【题意简化】给定一个 $n(\le10^5)$ 个点 $m(\le 2\times 10^5)$ 条边的带权($10^{18}$)图（不一定连通）。定义三元组 $(u,v,w)(1\le u < v \le n)$ 合法当且仅当存在从点 $u$ 到点 $v$ 存在一条边权异或和为 $w$ 的路径，经过多次的边需要算多次。求所有合法三元组的 $w$ 值之和对 $10^9+7$ 取模的值。

【分析】线性基与图论结合的一道计数好题。

如果直接枚举，肯定超时了，对于一个连通的图，图中的任意两点路径一定可以经过图中所有的环。那么我们可以 $dfs$ 整个图，d[x] 表示到根路径异或和，对于非树边 x->y , 对应就是一个环，环的异或和是 d[x]^d[y]^w。

在连通块内部，$x$ 到 $y$ 可以经过其他任意个环，环已经全部插入到线性基中，尝试统计所有 d[x]^d[y]^base 之和。

考虑每一个二进制位对答案的贡献，即考虑二进制第 $i$ 为取 $1$ 的方法数。

分两种情况，r 表示线性基中元素个数：

1.线性基中存在第 $i$ 位为 $1$ 的情况:

$k$ 表示线性基中第 $i$ 为 $1$ 的基的个数，那么为 $0$ 的基的个数即时 $r-k$.

取 $k$ 个基中奇数个，第 $i$ 位为 $1$ 的方法数: $num1=(C_k^1+C_k^3+\dots)*2^{(r-k)}=2^{k-1}*2^{(r-k)}=2^{r-1}$

取 $k$ 个基中偶数个，第 $i$ 位为 $0$ 的方法数: $num2=(C_k^2+C_k^2+\dots)*2^{(r-k)}=2^{k-1}*2^{(r-k)}=2^{r-1}$

我们发现在对于任意 x->y ,如果 d[x]^d[y] 第 $i$ 位为 $1$ ,那么基就取 $0$ ，第 $i$ 位对答案有贡献；反之，d[x]^d[y] 第 $i$ 位为 $0$ , 线性基内就取 $1$ ,第 $i$ 位对答案也有贡献。总之在基内第 $i$ 无论取 $0$ 还是取 $1$ ，第 $i$ 位对答案的贡献就是 $2^i*2^{r-1}*C_n^2$.

2.线性基中所有基第 $i$ 位为 $0$ 的情况:

线性基元素个数为 $r$ , 统计所有节点 $d[x]$ 第 $i$ 位为 $1$ 的节点数 $cnt$ , $num$ 是所有节点数 。如果要使得第 $i$ 位为 $1$ , 总方法数是 $cnt*(num-cnt)*2^r$ ，第 $i$ 位对答案的贡献就是 $cnt*(num-cnt)*2^r*2^i$

参考代码：点击

---

其他题目：

P5556 圣剑护符

P4839 P哥的桶

P5607 [Ynoi2013] 无力回天 NOI2017

CF959F Mahmoud and Ehab and yet another xor task

---

学习完毕

{{ select(1) }}

• YES
• NO