题解：P9731 [CEOI2023] Balance

MX-WF-C 8.14 最难题。

## 题意

给定一个 $n \times s$ 的矩阵。保证 $s$ 是 $2$ 的幂。你需要给出一种将矩阵的每一行重排的方案，使得对于每个矩阵中出现的数而言，在所有列中的出现次数的极差 $\le 1$。

## 做法

首先考虑 $s = 2$。不妨设这个矩阵形如 $[[u_1,v_1],[u_2,v_2]\dots[u_n,v_n]]$。

我们考虑将每个 $u_i, v_i$ 连无向边。我们断言，答案为给所有边定向，使得每个点的入度与出度的差的绝对值都 $\le 1$ 的方案数。

我们考虑一组答案与上述构造的映射关系。对于一条边而言，如果形如 $u_i \to v_i$，则将这一行的两个数交换（即 $[v_i, u_i]$）。否则如果 $u_i \gets v_i$，则这一行保持不变（即 $[u_i,v_i]$）。那么一个数被放在左边的行数即这个点的入度，右边的行数即出度。所以我们需要保证任意一个点的入度与出度的差的绝对值都 $\le 1$。

对于新问题，不难想到欧拉路的一系列东西。

若图中任意一点的度数均为偶数，那么我们对于每个连通块都求一遍**欧拉回路**。可以证明这样的情况下欧拉回路一定存在。那么我们可以根据这条欧拉回路轻易的构造出边的定向方案，且每个点的出度均等于入度。

若图中存在若干个点的度数为奇数。我们建一个 super 点与这些度数为奇数的点连边。可以证明度数为奇数的点的数量一定为偶数（因为所有点的度数和是边数的两倍，是个偶数，所以去除掉所有度数为偶数的点后，剩下的度数为奇数点的度数和也是偶数），即这个 super 点的度数为偶数。

所以这张新图就满足了上一种情况（即所有点的度数均为偶数）。跑一边欧拉回路，再将 super 点去掉即答案。这是因为原来的所有度数为奇数的点，在新图中满足了入度等于出度，所以去掉它的一个度之后，入度出度差至多为 $1$。

至此我们解决了 $s = 2$ 的情况。考虑更一般的问题。

分而治之好！设 $s = 2^k$。我们考虑将矩阵的**每一行**变形：

$$\begin{bmatrix}
a_{i,1}&a_{i,2}&\cdots&a_{i,2^{k-1}}&a_{i,2^{k-1} +1 }&\cdots&a_{i,2^k}
\end{bmatrix}

\longrightarrow

\begin{bmatrix}
a_{i,1} & a_{i,2^{k-1}+1} \\
a_{i,2} & a_{i,2^{k-1}+2} \\
\vdots & \vdots \\
a_{i,2^{k-1}} & a_{i,2^k}
\end{bmatrix}
$$

然后对于这个新矩阵执行上面的算法。换言之我们连边所有 $a_{i,j}, a_{i,j+2^{k-1}}$ 然后跑欧拉回路。

发现这样做我们能保证每个数字在 $a_{1\sim n,1 \sim 2^{k-1}}$ 中的出现次数与在 $a_{1\sim n, 2^{k-1}+1\sim 2^k}$ 中的出现次数相差至多 $1$。然后递归处理 $[1,2^{k-1}]$ 和 $[2^{k-1}+1, 2^k]$ 即可。

正在渲染内容...