线性基

题意给定 $n$ 行 $m$ 列的 $01$ 矩阵，求满足 $\big(\sum_{\forall i \in A, j \in B} value_{i, j}\big) \equiv 0 \pmod{2}$ 的二元组的数量 题解首先考虑 $n = 1$，令 $1$ 的个数为 $t$，可以发现答案$$\sum\limits_{k = 0}^{\lfloor\frac{m}{2}\rfloor} \dbinom{t}{2k} \times 2^{m - t} - 1 = 2^{m - 1} - 1$$至于证明，可以考虑已经选好的数列 $\{a_1, a_2, …, a_n\}$，那么现在考虑加入第 $n +1$ 个，显然加入 $0, 1$ 都是多了两种选择 那么现在考虑将行合并成一列 但是问题是如果需要枚举选的行还是需要 $2^n$ 的复杂度，然后我考场上就想到这就凉了 那么显然每次选好了行，再选列的时候这若干个列会贯穿所有行，那就可以将每行看作一个数，并且将它们合并（异或）起来，这样就变成做 $n = 1$ 的情况了 接下来只要考虑有几种情况会使得其异或和为 $1$ （或不为 $1$） ...

题目描述$\text{opt} = 1$ 时，代表把一个区间 $l, r$ 内的所有数都 $\text{xor}$ 上 $v$。 $\text{opt} = 2$ 时， 查询一个区间 $[l, r]$ 内选任意个数（包括 $0$ 个）数 $\text{xor}$ 起来，这个值与 $v$ 的最大 $\text{xor}$ 和是多少。 题解几乎没写过差分，看完这题之后顿时感觉到了差分的强大 首先显然第二个操作需要维护线性基，然后 $O (\log{n})$ 求解 然后因为有 $1$ 操作，所以若是直接维护区间线性基，在计算答案时不知道 $1$ 操作中的 $v$ 在当前答案中被异或上了奇数还是偶数次，故无法求解 但是在单点修改的情景下就不会有上述问题，故现在的问题是如何将区间问题转化为单点问题 于是就需要差分，让每个 $b_{i + 1} = a_{i + 1} ~ \text{xor} ~ a_i$，那么此时 $v$ 的贡献就只作用于 $b_l$ 与 $b_{r + 1}$，可直接单点修改，然后在线段树上同时维护区间线性基，查询时只需查询 $1…l$ 的前缀和（即 $b_l$），再将之 ...