【题解】CF662C Binary Table

CF662C Binary Table

给定一个 $n \times m$ 的 $01$ 矩阵，现在可以无限次对某一行或一列的每个数字取反，求最少的 $1$ 的个数。
$n \le 20\ ,\ m \le 10^5$

$\texttt{Solution}$

考虑 $n\le 20$，可以考虑把每一列压成一个二进制数字，然后 $2^{20}$ 枚举翻转哪些行。

对于一个枚举的行的翻转状态 $S$，令某一列原本的状态为 $p_i$，$f(x)$ 为 $x$ 二进制下 $1$ 的个数，那么翻转 $S$ 中的行后，这一列状态会变成 $p_i \oplus S$。这一列的 $1$ 的个数最少是 $min(f(p_i \oplus S),n - f(p_i \oplus S))$（可以选择是否翻转这一列）。

令 $a[x]$ 为 $x$ 这种状态在矩阵中出现的次数，$b[x]$ 为 $min(f(x),n - f(x))$。则对于一个状态 $S$，有：

$$ans[S] = \sum_{j} a[j] \times b[S \oplus j]$$

然后就可以写成：

$$ans[i] = \sum_{j \oplus k = i} a[j] \times b[k]$$

这是个 $\texttt{FWT}$ 的形式，直接上就完事了。
复杂度 $O(2^n \times log\ 2^n) = O(2^n \times n)$