题解：CF1993E Xor-Grid Problem

superl61 · 2024-11-06 19:46:42 · 题解

题目传送门

题意

给定一个 n \times m 的矩阵 a，有两种操作：

• 选择一行，把每个数变成所在列所有数的异或之和。
• 选择一列，把每个数变成所在行所有数的异或之和。

求进行任意次操作后整个矩阵最小的美丽值。

思路

第一个发现：同一数异或两次相当于没有异或，基于这个性质，我们首先可以发现连续两次对同一行（列）操作相当于没有操作。

第二个发现：能替换的值其实是很有限的，因为它是由一行或一列所有值的异或一起决定的，我们会忍不住把所有可供替换的值规规整整地写在对应行（列）前面，以样例中的第 4 组数据为例，我们把异或值写在第 0 行和第 0 列，可以得到：

你仔细观察这个矩阵或者手动操作几次，可以发现对某行（列）操作相当于和第 0 行（列）整体交换。

所以题目就转化成了：给定一个 (n + 1) \times (m + 1) 的矩阵 a，你可以不断地交换某一行和第 0 行，或者某一列和第 0 列，求最终矩阵（不包含第 0 行和第 0 列）最小的美丽值。

实现

交换次数是无限的，但矩阵的状态是有限的。

朴素想法是枚举所有的状态，全部求一遍美丽值。

肯定要枚举哪行哪列不选，还要枚举每行每列的排列方式，最后对整个矩阵求答案。所以直接做的话应该是 O(nm \times 2^{n + m} \times nm)，即 O((nm)^22^{n + m})。

首先可以发现其实行和列的贡献是分别独立的。以行为例，如果行的排列方式确定了，那竖着的贡献就是固定的。这是由操作方式决定的，题目给出的两种操作能保证初始同行（列）的元素到最后仍然同行（列），变的只是行之间和列之间的顺序。复杂度变为 O((nm)^2(2^nm + 2^mn)。

继续优化答案统计。每次都重新求一遍整个矩形的贡献实在是太不划算了。又想到对于一个选行（列）的集合 S，可以预先把最优的排列方式求出来，最后直接查。考虑状压 dp。

记 f_{S, i, j} 表示选的行集合为 S，最后一行是 i，不选第 j 列，最小美丽值。

记 g_{S, i, j} 表示选的列集合为 S，最后一列是 i，不选第 j 行，最小美丽值。

有转移

其中 sum_{i, k} 是某两行之间的总贡献，T 是 S 去掉 i。