【题解】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)$

添加新评论