adhoc 天地灭，线性代数保平安 | [EGOI 2024] Garden Decorations 题解
MatrixGroup
·
·
题解
题意
这是一道 multi-run 题。
给定正整数 n 和排列 p。有 a_0,a_1,\cdots,a_{n-1}\in \{0,1\}。先声明一个 w，你需要在接下来 w 次运行种按照以下方式修改 a，使得最终的 a_i 等于初始的 a_{p_i}，其中 p_i 是一个 0\sim n-1 的排列。
其中，第奇数轮运行中，你可以根据 a_0,a_1,\cdots,a_i 来决定把新的 a_i 修改成 0 还是 1。而第偶数轮运行中，你可以根据 a_i,a_{i+1},\cdots,a_{n-1} 来决定把新的 a_i 修改成 0 还是 1。
为了做到满分，你需要让 w\le 3。
## 题解
还没去尝试理解其它题解，来点线代。
考察能做到什么事情。首先一定不能丢信息，分析一下可以发现不丢信息的操作一定是让 $a_i$ 异或上关于之前知道的 $a_j$ 的一个函数。那么一个自然的想法是让 $a_i$ 异或上之前知道的一些 $a_j$ 的异或。
换言之，在 $\mathbb F_2$ 上，给定排列矩阵 $P$，要求找到矩阵 $M_1,M_2,M_3$（$M_i$ 代表第 $i$ 轮的操作），其中 $Pa=M_3M_2M_1a$（$a$ 是列向量）。而题目给出的限制相当于要求 $M_1,M_3$ 是下三角矩阵，$M_2$ 是上三角矩阵。加上可逆的条件是，就要求是单位上/下三角矩阵。
考察前两次操作的复合。$M_2M_1$ 可以是什么？或者说，一个可逆矩阵可以写成一个**上**三角矩阵乘以一个**下**三角矩阵的充要条件是什么？如果你学过线性代数的话，你可能更熟悉的是 LU 分解——一个可逆矩阵可以写成一个**下**三角矩阵乘以一个**上**三角矩阵，当且仅当它的每个顺序主子式（每个左上角 $k\times k$ 的子矩阵的行列式）都非零。那么，翻转过来，所有可能的 $M_2M_1$ 就是每个右下角 $k\times k$ 的子矩阵的都可逆的矩阵。（当然，如果没有学过的话，对着 Gauss 消元的过程推一下也能发现这一点。）
而我们希望 $M_3^{-1}P=M_2M_1$。单位下三角矩阵的逆当然也是单位下三角矩阵，而单位下三角矩阵左乘排列矩阵 $P$，就是把它的某些前面的行加到后面的行上去，也就是对于 $P$ 中的每一列，$1$ 之前不变，$1$ 之后可以是任何数。
举个例子来说，假如 $P$ 是
$$
\begin{bmatrix}
0&0&0&0&1&0&0\\
0&1&0&0&0&0&0\\
1&0&0&0&0&0&0\\
0&0&0&0&0&0&1\\
0&0&0&1&0&0&0\\
0&0&0&0&0&1&0\\
0&0&1&0&0&0&0\\
\end{bmatrix}
$$
的话，那么所有的 $M_3^{-1}P$ 就形如
$$
\begin{bmatrix}
0&0&0&0&1&0&0\\
0&1&0&0&?&0&0\\
0&?&0&1&?&0&0\\
0&?&0&?&?&0&1\\
1&?&0&?&?&0&?\\
?&?&0&?&?&1&?\\
?&?&1&?&?&?&?\\
\end{bmatrix}
$$
其中问号处可以填任何数。
那么最后要做的就是在每个问号处填上数，使得（在 $\mathbb F_2$ 上）每个右下角的 $k\times k$ 矩阵行列式都非零。
这是这个做法里最 ad-hoc 的一步，不过相信对于做到了这里的大家也不是很难。考虑到原矩阵自然可逆（无论如何都只有选这个排列对应的位置才能全 $1$），只需要让去掉第一行第一列的右下角子矩阵仍然符合要求即可。发现通过这样的操作可以让右下角的子矩阵仍然是一个符合同样要求的矩阵：（以上面那个矩阵为例）
$$
\begin{bmatrix}
0&0&0&0&1&0&0\\
\color{red}0&1&0&0&\color{blue}0&0&0\\
\color{red}0&?&0&1&\color{blue}0&0&0\\
\color{red}0&?&0&?&\color{blue}0&0&1\\
\color{red}1&?&0&?&\color{blue}1&0&?\\
\color{red}?&?&0&?&\color{blue}?&1&?\\
\color{red}?&?&1&?&\color{blue}?&?&?\\
\end{bmatrix}
$$
即，把第一列的剩下内容复制到第一行的 $1$ 所在的列。（如果第一行第一列就是 $1$ 就什么都不用做。）这样归纳构造即可。
本题直接 Gauss 消元和模拟上述过程即可做到 $O(n^3)$，足以通过，不需要写 `bitset` 除以 $w$ 之类的。
[代码](https://qoj.ac/submission/2399898)
[图：来自一位群友的评价]