AT_yahoo_procon2019_qual_e Solution

· · 题解

本篇题解最早在 2023-01-01 提交并通过，今天（2024-11-25）修改了一些表述。

Description

给出 n\times m 的 \verb!01! 矩阵，选择若干行和若干列，求有多少种选法满足选择的行列交点的异或和为 1。

## Solution 看到异或想到[线性基](https://www.luogu.com.cn/problem/P3812)。 我们不妨考虑一个经典问题：给定 $n$ 个数，问你有多少个子集满足异或和为 $0$。 这个题我们是这么做的：先给这 $n$ 个数建线性基，然后答案就是 $2^{n-\text{线性基的大小}}$。证明：线性基外的元素任选，选择一些线性基内的元素调整成 $0$。这是根据线性基和异或的定义来的。 这个 $0$ 当然可以换成任何数，只要能被异或出来就行。 --- 回到本题。 我们先从选择若干行下手。答案只可能和每一列分别异或起来有关。那么我们看异或后的结果。因为异或完也只有 $0, 1$，所以线性基的大小肯定是 $1$。那么看 $1$ 能否被线性基表示，就是问这个线性基里面元素是 $0$ 还是 $1$。 你一拍大腿，是 $0$ 不就相当于这堆数全 $0$ 吗！剩下的其他所有组合都有 $2^{m-1}$ 种选法（列的线性基的大小 $=1$）。 至于异或起来全 $0$ 行的个数......等等我们怎么又回到这个问题了？ 所以做完了，答案是 $(2^n - 2^{cnt})\times 2^{m-1}$，其中 $cnt$ 是 **把每一行看做一个 $\bm m$ 位二进制数** 得到的线性基大小。 时间复杂度 $\mathcal O(\dfrac{n^2m}{w})$。