题解：AT_yahoo_procon2019_qual_e Odd Subrectangles

· · 题解

先考虑最普通的题目。

给定 n 个数，问你有多少个子集满足异或和为 0。

这个题的解法很简单，就是建出一个线性基，那么答案就是 2^{n-\text{线性基内元素个数}}。

对于本题目我们先从选择若干行下手。答案只可能和每一列分别异或起来有关。 那么我们看异或后的结果。因为异或完也只有 $0,1$ 两种可能，所以线性基的大小肯定是 $1$。那么看 $1$ 能否被线性基表示，即为这个线性基里面是 $0$ 还是 $1$。 然后你发现如果这个是 $0$，那么这一堆均为 $0$，否则就有 $2^{m-1}$ 种情况。 那么这样子我们就可以把这一行看成一个 $m$ 为的二进制数。那么我们就可以把这几个数插入到线性基中。 那么答案即为 $(2^n-2^{线性基内元素个数}) \times 2^{m-1}$。