CF963-Div2-E. Xor-Grid Problem
题意
给定一个 \(n \times m\) 的矩阵 \(a\)，有两种操作：
- 选择一行，把每个数变成所在列所有数的异或之和。
- 选择一列，把每个数变成所在行所有数的异或之和。
求进行任意次操作后整个矩阵最小的美丽值。
思路
第一个发现：同一数异或两次相当于没有异或，基于这个性质，我们首先可以发现连续两次对同一行（列）操作相当于没有操作。
第二个发现：能替换的值其实是很有限的，因为它是由一行或一列所有值的异或一起决定的，我们会忍不住把所有可供替换的值规规整整地写在对应行（列）前面，以样例中的第 \(4\) 组数据为例，我们把异或值写在第 \(0\) 行和第 \(0\) 列，可以得到：
\[\begin{matrix} 1 & 2 & 15 & 12 \\ 0 & 1 & 2 & 3 \\ 7 & 4 & 5 & 6 \\ 6 & 7 & 8 & 9 \\ \end{matrix} \]你仔细观察这个矩阵或者手动操作几次，可以发现对某行（列）操作相当于和第 \(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\) 行，最小美丽值。
有转移
\[f_{S, i, j} = \min_{k \in S,k \ne i} f_{S \setminus \{i\}, k, j} + sum_{i, k} - \left| a_{i, j} - a_{k, j}\right| \]其中 \(sum_{i, k}\) 是某两行之间的总贡献。
\(g_{S, i, j}\) 转移同理。
最后答案就是
\[\min_{0 \le i \le n, 0 \le j \le m}(\min_{k \ne i}f_{U_1 \setminus \{i\}, k, j} + \min_{k \ne j}g_{U_2 \setminus \{j\}, k, i}) \]\(U_1, U_2\) 分别是行和列的全集。
时间复杂度 \(O(2^nn^2m + 2^mm^2n)\)。
注意 dp 三层循环的顺序，先枚举 \(S\)，再枚举 \(i\)，因为 \(S\) 是从小的更新到大的，而 \(i\) 是每一轮都枚举全部。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
int f[66000][18][18], g[66000][18][18];
int s[18][18], ss[18][18], a[18][18];
int T, n, m;
void init(){
cin >> n >> m;
F(s, 0, (1 << (n + 1)) - 1) F(i, 0, n) F(j, 0, m) f[s][i][j] = inf;
F(s, 0, (1 << (m + 1)) - 1) F(i, 0, m) F(j, 0, n) g[s][i][j] = inf;
F(i, 0, n) F(j, 0, n) s[i][j] = 0;
F(i, 0, m) F(j, 0, m) ss[i][j] = 0;
F(i, 1, n) F(j, 1, m) cin >> a[i][j];
F(j, 1, m){
a[0][j] = 0;
F(i, 1, n) a[0][j] ^= a[i][j];
}
F(i, 0, n){
a[i][0] = 0;
F(j, 1, m) a[i][0] ^= a[i][j];
} // ok
F(i, 0, n) F(k, i + 1, n) {
s[i][k] = 0;
F(j, 0, m) s[i][k] += abs(a[i][j] - a[k][j]);
s[k][i] = s[i][k];
}
F(i, 0, m) F(k, i + 1, m) {
ss[i][k] = 0;
F(j, 0, n) ss[i][k] += abs(a[j][i] - a[j][k]);
ss[k][i] = ss[i][k];
}
}
int solve(){
F(i, 0, n) F(j, 0, m) f[1 << i][i][j] = 0; // 只考虑行
F(j, 0, m) F(i, 0, n) g[1 << j][j][i] = 0; // 只考虑列
F(j, 0, m){
F(S, 1, (1 << (n + 1)) - 1){
F(i, 0, n){
if(!((S >> i) & 1) || f[S][i][j] == inf) continue;
F(k, 0, n){
if(i == k || ((S >> k) & 1)) continue;
f[S + (1 << k)][k][j] = min(f[S + (1 << k)][k][j], f[S][i][j] + s[i][k] - abs(a[i][j] - a[k][j]));
}
}
}
}
F(j, 0, n){
F(S, 1, (1 << (m + 1)) - 1){
F(i, 0, m){
if(!((S >> i) & 1) || g[S][i][j] == inf) continue;
F(k, 0, m){
if(i == k || ((S >> k) & 1)) continue;
g[S + (1 << k)][k][j] = min(g[S + (1 << k)][k][j], g[S][i][j] + ss[i][k] - abs(a[j][i] - a[j][k]));
}
}
}
}
int ans = inf, U1 = (1 << (n + 1)) - 1, U2 = (1 << (m + 1)) - 1;
F(i, 0, n){
F(j, 0, m){
int ret1 = inf;
F(k, 0, n) if(k != i) {
ret1 = min(ret1, f[U1 - (1 << i)][k][j]);
}
int ret2 = inf;
F(k, 0, m) if(k != j) {
ret2 = min(ret2, g[U2 - (1 << j)][k][i]);
}
ans = min(ans, ret1 + ret2);
}
}
return ans;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T --){
init();
cout << solve() << '\n';
}
return fflush(0), 0;
}