本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-14 17:14:14

这题被恶心了很久，不知道为啥一直没有题解。

做法

显然操作顺序不会影响结果，每一行或每一列最多操作一次。

注意到最多 $18$ 列，考虑暴力做法，先枚举哪些列执行了操作。

随后，枚举每一行，如果 $1$ 的数量大于 $0$ 的数量，就翻转这一行。

考虑将每一行视为一个二进制数。

问题转化为下面的形式：

给定一个长度为 $n$ 的非负整数序列 $b$，一个整数 $m$，每个数严格小于 $2^{m}$。
定义 $popcount(x)$ 为 $x$ 的二进制表示中 $1$ 的个数。
求出 $\min\limits_{x=0}^{2^m-1}\sum\limits_{i=1}^n\min(popcount(a_i\oplus x),m-popcount(a_i\oplus x))$。

设 $f_{s,i,j}$ 代表所有数异或 $s$，仅考虑最后 $i$ 位，二进制中 $1$ 的数量是 $j$ 的数有多少个。

遗憾的是，这样仍然很难设计转移方程，主要难点在于，新加入一位 $i'=i+1$ 之后，难以得到新的 $j'$。

考虑一些更严格的限制，$f_{s,i,j}$ 代表所有数异或 $s$，最后 $i$ 位中有 $j$ 位为 $1$，且前 $m-i$ 位都是 $0$ 的数字个数。

转移如下：

1. $f_{s,i,j} \leftarrow f_{s,i,j}+ f_{s,i-1,j}$，这个代表第 $i$ 位为 $0$ 的情况。
2. $f_{s,i,j} \leftarrow f_{s\oplus 2^i,i-1,j-1}$，代表第 $i$ 位为 $1$ 的情况。

另外，初始状态是 $f_{b_i,0,0}\leftarrow f_{b_i,0,0}+1$。