2022 年牛客多校加赛场 K 题题解

K Killer Sajin's Matrix

题意：给定 $n\times mn\backslash times\; m$ 的矩阵，要求在其中填入 $kk$ 个 $11$ 使得每行每列 $11$ 的个数均为奇数。输出一个合法方案或者报告无解。$n,m,k\le 1\times 10^{5}n,m,k\; \backslash leq\; 1\backslash times\; 10^5$。

解法：（感谢 Oscar 提供的做法）

显然通过不断的交换列与行可以使得所有的 $11$ 都安放在斜对角的矩阵中，且每行每列必然至少有一个 $11$，如下图的形态：

设每个满 $11$ 矩阵的长和宽分别为 $x_i,y_{i}x\_i,y\_i$，则有 $\sum x_i=n\backslash sum\; x\_i=n$，$\sum y_i=m\backslash sum\; y\_i=m$，同时 $\sum x_i{y}_i=k\backslash sum\; x\_iy\_i=k$。注意到 $x_i,y_{i}x\_i,y\_i$ 必然为奇数，则矩阵个数与 $n,m,kn,m,k$ 奇偶性相同，所以 $n,m,kn,m,k$ 的奇偶性必须完全相同。

考虑 $n,m,kn,m,k$ 均为奇数的情况。首先考虑一个 $3\times 33\backslash times\; 3$ 的基本型：

对于 $3\times 33\backslash times\; 3$ 的矩形，最少需要斜对角的 $33$ 个保证每行每列都有一个 $11$。可以通过删除中间的一个，增补周围的 $33$ 个变成一个 L 型，使用 $55$ 个 $11$。通过这一变换使得 $11$ 的个数增加了 $22$。

显然最少需要 $\max (n,m)\backslash max(n,m)$ 个 $11$，此时的放置方案为斜对角的放置 $\min (n,m)\backslash min(n,m)$ 个 $11$，再在最后一行放置 $\max (n,m)-\min (n,m)\backslash max(n,m)-\backslash min(n,m)$ 个 $11$，如下所示：

考虑当 $11$ 增多的时候如何修改。显然当 $k\le n+m-1k\; \backslash leq\; n+m-1$ 时，我们一直可以将一个 $3\times 33\backslash times\; 3$ 的斜对角通过删除中间一个 $11$，增加周围的 $33$ 个 $11$ 来增加两个 $11$：（该步操作可以称为 $3\to 53\backslash to\; 5$）

那么当我们达成了 $n+m-1n+m-1$：也就是周围第一列、最后一行全都是 $11$ 之后，对于内侧的 $(n-1)\times (m-1)(n-1)\backslash times\; (m-1)$，因为 $n-1,m-1n-1,m-1$ 均为偶数，因而可以一口气放上一个 $2\times 22\backslash times\; 2$ 而不影响任何的奇偶性：

但是这样的操作不会改变 $11$ 的个数对 $44$ 的余数。因而如果 $k-(n+m-1)\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}4)k-(n+m-1)\; \backslash equiv\; 2\backslash pmod\; 4$，则最后一步 $3\to 53\backslash to\; 5$ 操作不应当进行，以调整最后的余数。

注意到 $k=(n-1)(m-1)-2k=(n-1)(m-1)-2$ 是必然无解的：最后仅剩的两格必然会让所在的行或列不满足要求。

接下来考虑偶数的方案。同样基于该思想，首先构造一个 $kk$ 最小的答案：

然后以两行为基本单元开始不断调整（省略剩下的 $44$ 行），其基本原理还是逐步增加 $22$ 个格子：

最大的 $kk$ 为 $nm-\max (n,m)nm-\backslash max(n,m)$：即反选的答案。

可以参考 Oscar 的代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=53401391