CF1993E Xor-Grid Problem
Alex_Wei
·
·
题解
CF1993E Xor-Grid Problem
首先只考虑列操作。根据异或的性质，第 i 次操作会让被操作的列变为第 i - 1 次操作时被替换的列，于是可以这样想：我们手里拿着一列数，初始为每一行的所有数的异或和。每次用手里的列和某一列交换。对于行同理。
因此，对 1\leq i\leq n，设 a_{i, m + 1} 等于 a_{i, j} \ (1\leq j\leq m) 的异或和。对 1\leq j\leq m + 1，设 a_{n + 1, j} 等于 a_{i, j}\ (1\leq i\leq n) 的异或和，则每次操作相当于交换某一列和第 m + 1 列，或交换某一行和第 n + 1 行。
枚举删掉哪一行哪一列，剩下的行和列可以任意排列且行列贡献独立，预处理每两行之间和每两列之间的贡献，问题转化为最短哈密顿路径。使用 \mathcal{O}(2 ^ nn ^ 2) 的 DP 求解，总时间复杂度 \mathcal{O}(2 ^ n n ^ 4)，不能通过。
注意到在计算列之间的贡献时不需要枚举删掉哪一列，因为将第 m + 1 列加入 DP 后，删去一列可以直接在状态里进行操作。对于行同理。时间复杂度降为 \mathcal{O}(2 ^ nn ^ 3)。代码。