Trulicina 的网格构造 详细题解

问题重述

给定三个整数 $n, m, k$，满足 $k \ge 2$ 且 $n \cdot m \equiv 0 \pmod k$。要求构造一个 $n$ 行 $m$ 列的网格，每个格子填入 $1 \sim k$ 的整数，并满足：

1. 每个整数 $1 \sim k$ 在网格中出现的总次数相同（均为 $\frac{n\cdot m}{k}$ 次）；
2. 任意两个相邻（共享一条边）的格子中的整数不同。

题目保证这样的网格总是存在。

直观尝试：自然阅读顺序填充

一个直接的想法是，按照从上到下、从左到右的顺序，循环填入 $1, 2, \dots, k, 1, 2, \dots$。即第 $i$ 行第 $j$ 列（$0$‑based 索引，$i=0,\dots,n-1$，$j=0,\dots,m-1$）的数为：

$$a_{i,j} = ((i \cdot m + j) \bmod k) + 1.$$

例如，当 $n=3, m=4, k=6$ 时，得到：

1 2 3 4 5 6 1 2 3 4 5 6

该方案自动满足“每个数出现次数相等”，因为总共 $n\cdot m$ 是 $k$ 的倍数，循环填数恰好使每个 $1\sim k$ 都出现 $\frac{n\cdot m}{k}$ 次。

该方案何时失败？

检查相邻格子的差（模 $k$ 意义下）：

• 水平相邻：$a_{i,j+1} - a_{i,j} \equiv 1 \pmod k$（因为加 $1$）。只要 $k \ge 2$，$1 \not\equiv 0 \pmod k$，所以水平方向永远不会冲突。
• 垂直相邻：$a_{i+1,j} - a_{i,j} \equiv m \pmod k$（因为跨过一整行，索引增加 $m$）。因此，当 $m \not\equiv 0 \pmod k$ 时，垂直差不为 $0$，相邻不同；但当 $m$ 是 $k$ 的倍数时，$m \equiv 0 \pmod k$，导致 $a_{i+1,j} = a_{i,j}$，垂直相邻格子数字相同，违反条件。

例如 $n=4, m=6, k=3$：$m$ 是 $k$ 的倍数，自然顺序填入得到：

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

垂直相邻全是相同的数字，不符合要求。

修正方案：对部分行进行循环移位

当 $m$ 是 $k$ 的倍数时，我们需要通过“错位”来打破垂直相邻的相同。一个通用的构造是：仍然遵循逐行循环填充 $1\sim k$，但当检测到当前行与上一行在某一列出现相同数字时，将整行向左循环移动一个位置。

在实现中，我们逐行生成。对于第 $i$ 行，先按自然顺序生成一个临时行：

$$tmp_j = ((i \cdot m + j) \bmod k) + 1.$$

然后检查该行是否与上一行（存储在 LAST 中）有任何同列相同。若有，则将临时行循环左移一位，即新行 $CUR_j = tmp_{(j+1)\bmod m}$。再将 CUR 作为当前行输出，并把它更新为新的 LAST。

为什么一次循环移位就能修正？

设 $m$ 是 $k$ 的倍数，且第 $i-1$ 行的第 $j$ 列数字为 $x$。自然顺序下，第 $i$ 行同列的数字也是 $x$（因为 $m \equiv 0 \pmod k$）。进行循环左移一位后，原来位置 $j$ 的元素被原来位置 $j+1$ 的元素取代，即当前行 $j$ 列的数字变为 $((i \cdot m + j + 1) \bmod k) + 1$。

计算垂直差（模 $k$）：

$$\begin{aligned} CUR_j - LAST_j &\equiv \big( (i\cdot m + j + 1) - ((i-1)\cdot m + j) \big) \pmod k \\ &\equiv m + 1 \pmod k. \end{aligned} $$

由于 $m$ 是 $k$ 的倍数，$m \equiv 0 \pmod k$，故差为 $1 \pmod k$，不为 $0$。因此移位后，所有垂直相邻对均不同。

同时，移位操作保持水平相邻差仍为 $1$（或 $k-1$）。因为移一位后，整行仍是形如 $[s, s+1, \dots, k, 1, \dots, s-1]$ 的循环连续段，相邻位置仍差 $1 \pmod k$，不会相同。

图示示例

仍用 $n=4, m=6, k=3$：

• 第 1 行（$i=0$）：自然顺序 1 2 3 1 2 3，与上一行（空）不冲突，不移位。
• 第 2 行（$i=1$）：自然顺序 1 2 3 1 2 3，与上一行完全相同，触发移位。左移一位后变成 2 3 1 2 3 1。
• 第 3 行（$i=2$）：自然顺序 1 2 3 1 2 3，与上一行 2 3 1 2 3 1 比较，有同列相同吗？第 2 行第 2 列是 3，第 3 行自然顺序同列也是 3，所以移位。左移一位后变成 2 3 1 2 3 1 吗？但代码会继续判断。实际上标准程序在此场景下会交替出现 1 2 3 1 2 3 和 2 3 1 2 3 1，最终输出正与题面示例一致：

1 2 3 1 2 3 2 3 1 2 3 1 1 2 3 1 2 3 2 3 1 2 3 1

垂直相邻差为 $1 \pmod k$，水平差也为 $1 \pmod k$，完美符合条件。

当 $m$ 不是 $k$ 的倍数时

此时自然顺序已经满足条件，shift 始终为 false，不会移位。输出即为自然顺序填充。

特判：$m = 1$

当 $m = 1$ 时，网格只有一列，不存在水平相邻限制。唯一要求是垂直相邻不同且每个数出现次数相等。我们可以简单地让第 $i$ 行填 $(i \bmod k) + 1$，这样相邻行差为 $1 \pmod k$，且每个数字恰好出现 $\frac{n}{k}$ 次（因为 $n$ 是 $k$ 的倍数）。

标准程序中对 $m=1$ 做了特殊处理，直接输出，不进入后续逻辑。

算法流程

1. 读入 $t$。
2. 对每个测试用例：

• 读入 $n, m, k$。
• 若 $m = 1$：
  • 对于 $i = 0 \dots n-1$，输出 $(i \bmod k) + 1$，并换行。
  • 继续下一个用例。
• 初始化数组 LAST 长度为 $m$，值全为 $-1$（表示上一行，初始无限制）。
• 对于 $i = 0 \dots n-1$：
  • 创建当前行数组 CUR 长度为 $m$。
  • shift = false
  • 对于 $j = 0 \dots m-1$：
    • elm = ((i * m + j) % k) + 1
    • CUR[j] = elm
    • 若 elm == LAST[j]，则 shift = true
  • 若 shift 为真：
    • 将 CUR 循环左移一位：newCUR[j] = CUR[(j + 1) % m]
    • 用 newCUR 替换 CUR
  • 输出 CUR 的 $m$ 个整数，空格分隔，行末换行。
  • LAST = CUR（更新上一行）。

正确性证明

每个数字出现次数相等

无论是自然顺序还是经过移位，每一行都是 $1 \sim k$ 的某个循环排列的重复。具体来说，若一行有 $m$ 个元素，且 $k$ 整除 $m$（因为我们只在 $m$ 是 $k$ 的倍数时才移位，而 $m$ 不是 $k$ 的倍数时不移位），那么这一行恰好包含完整的 $\frac{m}{k}$ 套 $1 \sim k$。当 $m$ 不是 $k$ 的倍数时，整行仍由若干个完整周期和一个部分周期组成，但整个网格总元素数 $n\cdot m$ 是 $k$ 的倍数，且每行的填充方式都是连续的块，可以证明每种数字出现的总次数为 $\frac{n\cdot m}{k}$。

更严谨的论证：无论是否移位，第 $i$ 行第 $j$ 列的数字总可以写成 $((i\cdot m + j + \delta_i) \bmod k) + 1$ 的形式，其中 $\delta_i \in \{0, -1\}$（不移位时 $\delta_i = 0$，移位时相当于 $\delta_i = -1$）。整个网格的数字序列是将 $0 \sim n\cdot m - 1$ 的连续整数加上每行的偏移后对 $k$ 取模。由于每行的偏移都是常数，且 $n\cdot m$ 是 $k$ 的倍数，容易得知每个余数出现的次数完全相等。

相邻格子不同

• 水平相邻：不移位时差为 $1$；移位后由于整行循环左移，相邻元素在模意义下仍相差 $1$（原来是连续的数，循环移位后依然是连续的数）。因此水平相邻永不相同。
• 垂直相邻：
• 若 $m \not\equiv 0 \pmod k$，不移位，差为 $m \not\equiv 0$，不同。
• 若 $m \equiv 0 \pmod k$，当不移位时垂直差为 $0$，但此时必然有同列相同导致 shift = true，因此一定会移位。移位后垂直差变为 $m + 1 \equiv 1 \pmod k$，不同。

因此所有相邻对均不相同。

复杂度分析

对于每个测试用例，我们逐行逐列生成网格，时间复杂度为 $O(n \cdot m)$。由于所有测试用例的 $n \cdot m$ 之和不超过 $2 \times 10^5$，总时间完全在限制内。空间复杂度同样为 $O(m)$，只需存储当前行和上一行。

总结

本题通过简单的“自然顺序+条件移位”构造，巧妙解决了当列数是 $k$ 的倍数时垂直相邻冲突的问题。关键在于分析垂直相邻差 $m \bmod k$，并通过一行循环移位将差调整为 $1 \bmod k$，同时不影响水平相邻的性质。这种构造方法简洁且易于实现，是 CF 中典型的有趣构造题。

标准程序

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        // 特判 m == 1 的情况：行内没有相邻限制，只需行间不同且每个数出现相等
        if (m == 1) {
            for (int i = 0; i < n; ++i) {
                cout << (i % k) + 1 << '\n';
            }
            continue;
        }
        vector<int> LAST(m, -1);
        for (int i = 0; i < n; ++i) {
            vector<int> CUR(m);
            bool shift = false;
            for (int j = 0; j < m; ++j) {
                int elm = ((i * m + j) % k) + 1;
                CUR[j] = elm;
                if (elm == LAST[j]) {
                    shift = true;
                }
            }
            if (shift) {
                // 循环左移一位（对应 Python 的 CUR[(j+1)%m]）
                vector<int> newCUR(m);
                for (int j = 0; j < m; ++j) {
                    newCUR[j] = CUR[(j + 1) % m];
                }
                CUR = move(newCUR);
            }
            for (int j = 0; j < m; ++j) {
                cout << CUR[j] << " \n"[j == m - 1];
            }
            LAST = CUR;
        }
    }
    return 0;
}