题解

思路

把一列从上到下的二进制数看成一个 $n$ 位掩码 $x$，记相同掩码的列数为 $c_x$。假设被翻转的行集合为掩码 $s$，那么该列变为 $x\mathbin{\mathrm{xor}}s$。

行操作确定后，每一列是否翻转可以独立决定。若当前列有 $k$ 个 $1$，不翻转的代价是 $k$，翻转的代价是 $n-k$，故该列的最优贡献为

$$w(x)=\min(\operatorname{popcount}(x),n-\operatorname{popcount}(x)).$$

于是选择行掩码 $s$ 后的答案为

$$F_s=\sum_x c_xw(x\mathbin{\mathrm{xor}}s),$$

这正是两个长度为 $2^n$ 的数组的异或卷积。用 Walsh--Hadamard 变换即可一次求出全部 $F_s$。

做法

子任务 1：枚举行、列翻转集合

枚举 $2^n$ 个行集合和 $2^m$ 个列集合，直接统计翻转后的 $1$。复杂度为 $O(2^{n+m}nm)$。

子任务 2：枚举行集合，贪心选择每一列

只枚举 $2^n$ 个行翻转集合。对每个集合扫描全部列，并把每列贡献取为 $\min(k,n-k)$。复杂度为 $O(m2^n)$。

子任务 3：异或卷积

统计 $c_x$，构造 $w_x$。分别对两个数组做异或 FWT，逐点相乘，再做逆变换，得到所有 $F_s$，取最小值。复杂度为 $O(m+n2^n)$。

正确性证明

引理 1

固定行翻转集合 $s$ 后，掩码为 $x$ 的列对答案的最小贡献是 $w(x\mathbin{\mathrm{xor}}s)$。

证明。 行翻转后该列的 $1$ 的数量为 $k=\operatorname{popcount}(x\mathbin{\mathrm{xor}}s)$。列不翻转贡献 $k$，列翻转贡献 $n-k$；两者取小即得结论。$\square$

引理 2

异或卷积得到的第 $s$ 项等于固定行翻转集合 $s$ 时的最优答案。

证明。 异或卷积第 $s$ 项为 $\sum_x c_xw(x\mathbin{\mathrm{xor}}s)$。由引理 1，式中每项恰是对应各列独立选择是否翻转后的最小贡献，求和即得固定 $s$ 的最优答案。$\square$

定理

算法输出所有合法操作序列中最少的 $1$ 的数量。

证明。 任意操作序列都唯一对应一个行翻转集合，以及在该集合确定后对各列的翻转选择。引理 2 给出每个行集合下最优的列选择；枚举卷积的全部位置并取最小值，因而覆盖所有操作方案并取得全局最优值。$\square$

复杂度

时间复杂度为 $O(m+n2^n)$，空间复杂度为 $O(2^n)$。