ABC396G 题解

__vector__ · 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 的数字个数。

转移如下：

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