【题解】CF662C Binary Table

CF662C Binary Table

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

$\mathtt{\text{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]$$

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