2026 杭电春季联赛 3——1006-骰子大战（一定要好好读题，把题面中的所有限制信息都读到）

题目大意

题目描述
需要构造 $n$ 个具有 $k$ 个面的骰子，每个面上的数字取值范围为 $0 \sim m$。
两个骰子进行对决时，随机掷出一个面，点数大者获胜。要求构造的骰子组合必须同时满足以下三个条件：

1. 循环劣势：形成 $1 \to 2 \to 3 \to \dots \to n-1 \to n \to 1$ 的胜负关系。即 1 号骰子输给 2 号，2 号输给 3 号，……，$n$ 号输给 1 号（“输给”定义为在 $k \times k$ 种可能的掷出组合中，获胜的次数严格少于对方）。

2. 绝对无平局：每个数字至多只能出现在一个骰子上，保证任意两个骰子对决时不可能掷出相同的点数。

3. 字典序最小：将 1 号到 $n$ 号骰子上的所有数字按顺序拼接成一个长度为 $n \times k$ 的序列，要求该序列在所有合法方案中字典序最小。

输入格式
第一行输入一个正整数 $T$，表示测试数据组数。
接下来每组数据输入三个正整数 $n$、$m$、$k$，分别表示骰子数量、面上的最大允许数字、每个骰子的面数。

输出格式
对于每组数据，输出一行 $n \times k$ 个用空格分隔的整数，依次表示 1 号到 $n$ 号骰子各个面上的数字。

样例数据

输入样例：

1
3 4 3

输出样例：

0 3 3 1 1 4 2 2 2

样例解释
输入代表需要构造 $3$ 个骰子，每个骰子有 $3$ 个面，数字范围在 $0 \sim 4$ 之间。根据输出样例，三个骰子的构造如下：

• 1 号骰子：[0, 3, 3]

• 2 号骰子：[1, 1, 4]

• 3 号骰子：[2, 2, 2]

胜负关系验证（总对决情况数为 $3 \times 3 = 9$ 种）：

• 1 号 vs 2 号：1 号获胜的情况为 3>1（共 4 次），2 号获胜的情况为 1>0、1>0、4>0、4>3、4>3（共 5 次）。2 号胜率更高，1 号输给 2 号。

• 2 号 vs 3 号：2 号获胜的情况为 4>2（共 3 次），3 号获胜的情况为 2>1（共 6 次）。3 号胜率更高，2 号输给 3 号。

• 3 号 vs 1 号：3 号获胜的情况为 2>0（共 3 次），1 号获胜的情况为 3>2（共 6 次）。1 号胜率更高，3 号输给 1 号。

该方案数字各不相同（无平局），构成了 $1 \to 2 \to 3 \to 1$ 的循环劣势，且可以证明拼接后的序列 0 3 3 1 1 4 2 2 2 是所有满足条件的方案中字典序最小的。

思路讲解

gemini 的思路以及代码

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=17028
这道题是一道非常精妙的构造题，涉及博弈与贪心策略。为了得到字典序最小的方案，我们需要深入分析骰子胜负的数学本质。

题目描述

我们需要构造 $n$ 个具有 $k$ 个面的骰子，每面的数字范围为 $0 \sim m$。要求形成 $1 \to 2 \to 3 \to \dots \to n \to 1$ 的循环劣势（即 $i+1$ 击败 $i$，$1$ 击败 $n$），其中“击败”定义为在 $k^2$ 次可能对决中获胜次数严格大于一半。不仅要满足该条件，还要使所有骰子的面按顺序拼接后的序列字典序最小。

解题思路

1. 胜负条件的数学转化：
由于不能平局，任意两个骰子对决共有 $k^2$ 种结果。“$B$ 击败 $A$” 等价于 $B$ 在对决中获胜的次数 $W(B, A) \ge \lfloor k^2/2 \rfloor + 1$。
令目标获胜次数为 $w = \lfloor k^2/2 \rfloor + 1$。
2. 字典序最小的贪心框架：
为了让整体拼接成的序列字典序最小，我们需要让 $1$ 号骰子的数字尽可能小，且小数字尽可能多；接着是 $2$ 号骰子，依此类推。
这启发我们设计一种 “两阶段划分（双段构造）” 的模式。将每个骰子 $i$ 的 $k$ 个面分成两部分：

• 早段（较小的数字）：包含 $x_i$ 个面。
• 晚段（较大的数字）：包含 $y_i = k - x_i$ 个面。
  为了最小化序列，我们按照如下顺序分配逐渐递增的数值：
  $1$ 号早段 $\to 2$ 号早段 $\dots \to n$ 号早段 $\to 1$ 号晚段 $\to 2$ 号晚段 $\dots \to n$ 号晚段。
  同一段内的面赋予完全相同的数字，不同段赋予递增的数字。
  3. 推导核心不等式：
  在上述赋值顺序下，考虑相邻骰子的对决：
• $i+1$ 击败 $i$ ($1 \le i < n$)：
  $i+1$ 的“早段”排在 $i$ 的“早段”之后，所以能赢 $x_{i+1} \times x_i$ 次。
  $i+1$ 的“晚段”排在 $i$ 的两段之后，所以能赢 $y_{i+1} \times k$ 次。
  总获胜次数：$x_{i+1} x_i + (k - x_{i+1}) k \ge w$
  化简得：$x_{i+1} (k - x_i) \le k^2 - w$。令 $R = k^2 - w$，即 $x_{i+1} (k - x_i) \le R$。
• $1$ 击败 $n$：
  $1$ 的“早段”排在最前面，赢不了 $n$ 的任何面。
  $1$ 的“晚段”排在 $n$ 的“早段”之后、“晚段”之前，所以能赢 $y_1 \times x_n$ 次。
  总获胜次数：$y_1 x_n = (k - x_1) x_n \ge w$。
  4. 贪心求解 $x_i$：
  要使字典序最小，我们要尽可能让早段容量变大（即尽量最大化 $x_1, x_2, \dots$）：
• 由 $(k - x_1) x_n \ge w$，且 $x_n \le k$，可知 $(k - x_1) k \ge w$，即 $x_1 \le k - \lceil w/k \rceil$。我们直接取最大值：$x_1 = k - \lceil w/k \rceil$。
• 对于后续的 $x_i$ ($i \ge 2$)，根据 $x_i (k - x_{i-1}) \le R$，只要 $k - x_{i-1} > 0$，我们就贪心地取最大合法值：$x_i = \min(k, \lfloor R / (k - x_{i-1}) \rfloor)$。
  （如果 $x_{i-1} = k$，意味着 $i$ 号骰子可以无条件获胜，此时直接设 $x_i = k$）。
  由于题目保证解存在，$m$ 必定足够大，我们只需依据 $x_i$ 和 $y_i$ 生成非空的段并依次赋上递增的数字即可。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    long long n, m, k;
    if (!(cin >> n >> m >> k)) return;

    // w 为获胜所需的最少胜场数，R 为不等式中的常数上限
    long long w = (1LL * k * k) / 2 + 1;
    long long R = 1LL * k * k - w; // 即 ceil(k^2 / 2) - 1

    vector<long long> x(n + 1);

    // 确定贪心的最优化分段容量
    x[1] = k - (w + k - 1) / k; // k - ceil(w / k)
    for (int i = 2; i <= n; i++) {
        long long denom = k - x[i - 1];
        if (denom == 0) {
            x[i] = k;
        } else {
            x[i] = min((long long)k, R / denom);
        }
    }

    // 记录分配的具体数字，用 -1 初始化
    long long current_val = 0;
    vector<long long> early_val(n + 1, -1);
    vector<long long> late_val(n + 1, -1);

    // 首先按顺序分配给所有存在的“早段”
    for (int i = 1; i <= n; i++) {
        if (x[i] > 0) {
            early_val[i] = current_val++;
        }
    }
    // 然后按顺序分配给所有存在的“晚段”
    for (int i = 1; i <= n; i++) {
        long long y = k - x[i];
        if (y > 0) {
            late_val[i] = current_val++;
        }
    }

    // 按要求输出 n*k 个序列数字
    bool first = true;
    for (int i = 1; i <= n; i++) {
        // 输出早段的数字
        for (int j = 0; j < x[i]; j++) {
            if (!first) cout << " ";
            cout << early_val[i];
            first = false;
        }
        // 输出晚段的数字
        long long y = k - x[i];
        for (int j = 0; j < y; j++) {
            if (!first) cout << " ";
            cout << late_val[i];
            first = false;
        }
    }
    cout << "\n";
}

int main() {
    // 提升 I/O 效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：计算所有的段落分布 $x_i$ 只需要一重循环遍历 $1$ 到 $n$。为骰子面赋值和打印输出的循环总计处理了 $n \times k$ 次操作。所以处理每组测试数据的时间复杂度为 $\mathcal{O}(n \times k)$。结合总和 $\sum n \times k \le 2 \times 10^5$，算法能在极短时间内高速执行完成。
• 空间复杂度：由于只存储了诸如 x、early_val 和 late_val 这些一维状态数组，占用空间为 $\mathcal{O}(n)$。这远低于题目宽松的 $512 \text{ MB}$ 空间限制。

gemini 的 latex 代码

\documentclass{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

% 保持与模板一致的 minted 样式
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

\begin{document}

\begin{center}
    \section*{骰子大战}
\end{center}

\subsection*{题目大意}
有 $n$ 个具有 $k$ 个面的骰子，每面的数字范围为 $0 \sim m$。需要构造一种赋值方案，使得 $i+1$ 号骰子击败 $i$ 号骰子（其中 $1 \le i < n$），并且 $1$ 号骰子击败 $n$ 号骰子。这里的“击败”定义为：两个骰子组合的 $k^2$ 种对决结果中，获胜次数严格大于一半。

同时要求在所有满足上述循环劣势条件的方案中，将 $1$ 号到 $n$ 号骰子的所有面按顺序拼接后的序列\textbf{字典序最小}。题目保证解一定存在。

\subsection*{解题思路}

这道题的核心难点在于平衡“循环劣势”与“字典序最小”这两个看似矛盾的条件。我们将推导过程分为动机分析、构造模型、条件转化和贪心求解四个部分。

\subsubsection*{1. 动机分析与核心思想}

要求最终拼接的序列字典序最小，意味着我们应当\textbf{优先让编号越小的骰子分配到越小的数字}，并且\textbf{小数字的数量应当尽可能多}。

如果我们遵循最朴素的贪心思想，直接把最小的一批数字全部分给 $1$ 号骰子，稍大一些的分给 $2$ 号骰子，以此类推，那么显然 $n$ 号骰子将拥有最大的数字。这样确实能保证 $i+1$ 击败 $i$，但会面临一个致命问题：$1$ 号骰子的数字太小，绝对无法击败 $n$ 号骰子，从而无法形成题目要求的闭环（即 $1 \to 2 \to \dots \to n \to 1$）。

为了打破这个僵局，我们必须让 $1$ 号骰子拥有\textbf{少部分非常大的数字}，大到足以在与 $n$ 号骰子的对决中获得足够的胜场。但为了不破坏字典序最小的要求，这些大的数字必须尽可能排在序列的后方。这就自然引出了“双段构造”的思想。

\subsubsection*{2. 双段构造法模型}

我们将每个骰子的 $k$ 个面拆分为两个集合：
\begin{itemize}
    \item \textbf{早段（分配较小的数字）}：设第 $i$ 号骰子的早段分配了 $x_i$ 个面。同一个骰子的所有早段面填写的数字完全相同。
    \item \textbf{晚段（分配较大的数字）}：设第 $i$ 号骰子的晚段分配了 $y_i \leftarrow k - x_i$ 个面。同一个骰子的所有晚段面填写的数字完全相同。
\end{itemize}

如你所见，为了满足“字典序最小”，我们将较小的数字优先分配给靠前的骰子，于是天然形成了两个内部递增的顺序：$\text{早段}_1 < \dots < \text{早段}_n$ 以及 $\text{晚段}_1 < \dots < \text{晚段}_n$。

但\textbf{为什么早段和晚段之间，必须是完全割裂的“所有的早段都小于所有的晚段”}（即 $\text{早段}_n < \text{晚段}_1$）呢？能不能把它们的大小关系穿插一下？

这个强行不穿插的规定，是由\textbf{“$1$ 号骰子必须击败 $n$ 号骰子”这个游戏规则倒逼出来的。}
\begin{itemize}
    \item \textbf{如果穿插了会发生什么（反证法）？} 
    假设我们不这么分，而是让 $\text{晚段}_1 < \text{早段}_n$。
    因为对于任何一个骰子来说，它的早段肯定小于它的晚段，所以 $\text{早段}_1 < \text{晚段}_1$。
    如果 $\text{晚段}_1 < \text{早段}_n$，那么对 $1$ 号骰子来说，它的\textbf{所有数字}（$\text{早段}_1$ 和 $\text{晚段}_1$）就都严格小于 $n$ 号骰子的 $\text{早段}_n$ 了。
    这意味着，$1$ 号骰子的\textbf{最大面}，都比 $n$ 号骰子的\textbf{最小面}还要小。那 $1$ 号骰子打 $n$ 号骰子的胜率直接就是 $0$，绝对不可能击败 $n$ 号。
    \item \textbf{破局的唯一方式}：
    为了让 $1$ 号能够击败 $n$ 号，$1$ 号骰子必须拥有一些能够大过 $n$ 号的数字。为了不破坏整体序列尽量小的字典序，我们把这些大数字安排在 $1$ 号骰子的末尾（也就是 $\text{晚段}_1$）。为了让这部分数字能赢过 $n$ 号，它至少必须大过 $n$ 号最小的那批数字（也就是 $\text{早段}_n$）。
    \item \textbf{贪心衔接形成最终顺序}：
    因此，$\text{晚段}_1$ 被强行拔高，必须放在 $\text{早段}_n$ 之后，即确立了不可逾越的界限：$\text{早段}_n < \text{晚段}_1$。
    而在确立了这个界限之后，剩下的数字继续按照字典序贪心法则，依次递增地分配给 $\text{晚段}_1 \to \text{晚段}_2 \to \dots \to \text{晚段}_n$。
\end{itemize}

这就是最终的全局数值大小分配顺序必须为以下形式的原因：
$$ \text{早段}_1 < \text{早段}_2 < \dots < \text{早段}_n < \text{晚段}_1 < \text{晚段}_2 < \dots < \text{晚段}_n $$

\subsubsection*{3. 胜负条件的代数推导}

任意两个骰子对决没有平局，共有 $k^2$ 种结果。要实现“击败”，获胜次数必须大于等于 $w \leftarrow \lfloor k^2/2 \rfloor + 1$。

在双段构造的大小关系下，我们来计算对决的胜场数：

\textbf{第一种情况：$1$ 号骰子击败 $n$ 号骰子}

$1$ 号的“早段”是全局最小的，无法击败 $n$ 号的任何面；
$1$ 号的“晚段”仅大于 $n$ 号的“早段”（因为 $\text{晚段}_1 < \text{晚段}_n$），因此 $1$ 号获胜的次数完全由“$1$ 号晚段”对战“$n$ 号早段”贡献。
所以 $1$ 号的总获胜次数为 $y_1 \times x_n$。我们需要满足：
$$ (k - x_1) \times x_n \ge w $$

\textbf{第二种情况：$i+1$ 号骰子击败 $i$ 号骰子（对于 $1 \le i < n$）}

\begin{itemize}
    \item $i+1$ 号的“早段”排在 $i$ 号的“早段”之后，所以能击败 $i$ 号的“早段”，贡献胜场 $x_{i+1} \times x_i$。
    \item $i+1$ 号的“晚段”排在 $i$ 号的“晚段”之后，自然也大于 $i$ 号的“早段”，所以能击败 $i$ 号的所有面，贡献胜场 $y_{i+1} \times k$。
\end{itemize}

总获胜次数要求：
$$ x_{i+1} \times x_i + y_{i+1} \times k \ge w $$
将 $y_{i+1} \leftarrow k - x_{i+1}$ 代入并化简：
$$ x_{i+1} \times x_i + k^2 - x_{i+1} \times k \ge w $$
$$ x_{i+1} \times (k - x_i) \le k^2 - w $$

为了方便，我们令常数 $R \leftarrow k^2 - w$。核心不等式即为：
$$ x_{i+1} \times (k - x_i) \le R $$

\subsubsection*{4. 贪心求解 $x_i$}

为了使字典序最小，我们需要让每个骰子尽量多地获得“早段”的容量（即小数字）。因此我们要尽可能地\textbf{最大化} $x_1$，$x_2$，$\dots$，$x_n$。

\begin{itemize}
    \item \textbf{确定 $x_1$}：根据 $1$ 击败 $n$ 的条件 $(k - x_1) \times x_n \ge w$。由于 $x_n$ 的理论最大值为 $k$，要使 $x_1$ 尽可能大，就必须让 $(k - x_1)$ 尽可能小。最极限的情况是 $x_n$ 达到最大值 $k$，此时：
    $$ (k - x_1) \times k \ge w \implies k - x_1 \ge \left\lceil \frac{w}{k} \right\rceil $$
    因此，我们贪心地取 $x_1$ 的最大合法值：
    $$ x_1 \leftarrow k - \left\lceil \frac{w}{k} \right\rceil $$

    \item \textbf{确定 $x_{i}$（对于 $i \ge 2$）}：基于不等式 $x_i \times (k - x_{i-1}) \le R$，我们要贪心地让 $x_i$ 尽可能大：
    \begin{itemize}
        \item 如果 $k - x_{i-1} > 0$，则：
        $$ x_i \leftarrow \min\left(k, \left\lfloor \frac{R}{k - x_{i-1}} \right\rfloor\right) $$
        \item 如果 $x_{i-1} \leftarrow k$，意味着 $i-1$ 号骰子全部分配为早段。此时无论 $x_i$ 取何值，$i$ 号骰子的晚段都能击败 $i-1$ 号的全部面（晚段大于一切早段）。因此可以直接贪心地让 $x_i \leftarrow k$。
    \end{itemize}
\end{itemize}

题目保证解一定存在，所以按照上述方式递推求出所有的 $x_i$ 后，我们依次给存在的早段和晚段分配严格递增的数值即可。

\subsection*{代码实现}

\begin{minted}{cpp}
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    long long n, m, k;
    if (!(cin >> n >> m >> k)) return;

    // w 为获胜所需的最少场数
    long long w = (1LL * k * k) / 2 + 1;
    // R 为推导出的常数界限
    long long R = 1LL * k * k - w;

    vector<long long> x(n + 1);
    
    // 贪心确定 1 号骰子的最大早段容量
    x[1] = k - (w + k - 1) / k; 
    
    // 递推贪心确定后续骰子的最大早段容量
    for (int i = 2; i <= n; i++) {
        long long denom = k - x[i - 1];
        if (denom == 0) {
            x[i] = k;
        } else {
            x[i] = min((long long)k, R / denom);
        }
    }

    // current_val 用于按顺序分配递增的数值
    long long current_val = 0;
    vector<long long> early_val(n + 1, -1);
    vector<long long> late_val(n + 1, -1);

    // 阶段一：按顺序给所有骰子的“早段”分配小数值
    for (int i = 1; i <= n; i++) {
        if (x[i] > 0) {
            early_val[i] = current_val++;
        }
    }
    // 阶段二：按顺序给所有骰子的“晚段”分配大数值
    for (int i = 1; i <= n; i++) {
        long long y = k - x[i];
        if (y > 0) {
            late_val[i] = current_val++;
        }
    }

    // 按照 1 到 n 号骰子的顺序，格式化输出所有的面
    bool first = true;
    for (int i = 1; i <= n; i++) {
        // 输出早段
        for (int j = 0; j < x[i]; j++) {
            if (!first) cout << " ";
            cout << early_val[i];
            first = false;
        }
        // 输出晚段
        long long y = k - x[i];
        for (int j = 0; j < y; j++) {
            if (!first) cout << " ";
            cout << late_val[i];
            first = false;
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}
\end{minted}

\subsection*{复杂度分析}
\begin{itemize}
    \item \textbf{时间复杂度}：贪心推导 $x_i$ 的过程仅需一次遍历，时间复杂度为 $\mathcal{O}(n)$。为每个面输出数值的过程需要两层循环，执行次数恰好为 $\sum_{i=1}^n x_i + y_i = n \times k$。因此总时间复杂度为 $\mathcal{O}(n \times k)$，非常高效。
    \item \textbf{空间复杂度}：存储状态数组及对应的分配数值所需的数组长度均为 $n+1$，整体占用空间为 $\mathcal{O}(n)$，能够轻松满足题目要求。
\end{itemize}

\end{document}

首先，我们为什么会想到双段构造？呃，其实正常的思维链路应该是，我们先想怎么构造，

其实题面里面讲的非常清楚，一个骰子最多只会有两种不同的数字，每个数字仅能出现在至多一个骰子上。

那都说了，最多两个数，那还能不是双段构造吗？

如果分成双段构造，那么不难看出：

$\text{早段}_1 < \text{早段}_2 < \dots < \text{早段}_n$，$\text{晚段}_1 < \text{晚段}_2 < \dots < \text{晚段}_n $（为了字典序最小，这两个条件是必须的），但是早晚段之间是什么关系呢？

注意啊，为了赢得游戏，$\text{早段}_n < \text{晚段}_1$，这个也是为了赢得游戏，满足所谓的“循环劣势要求”，所必须的这个构造，一个的最小的，大于一个的最大的，两者之间是绝对不会发生这个穿插的这个情况的，因此就是 $\text{早段}_1 < \text{早段}_2 < \dots < \text{早段}_n < \text{晚段}_1 < \text{晚段}_2 < \dots < \text{晚段}_n$。

okay，那这道题目比较关键的部分就做完了，当然，还需要处理一些细节问题，就是每个段的早段是几个数，晚段是几个数？

不过贪心求解的部分也不是那么容易的。

首先，先写出一系列的这个获胜条件：

接着，我们要进行这个贪心求解，我们不难发现：

然后我们知道了 x1 的值，后面就用前面的限制，一个一个往后推就行了。

void gen_eraly_seg() {
    for (int i = 1; i <= N; ++i) {
        ll early_sz;
        if (i == 1) {
            early_sz = K - (bound_win + K - 1) / K;
        } else {
            if (early_sz_ls[i - 1] - K == 0) {
                early_sz = K;
            } else {
                early_sz = (bound_win - K * K) / (early_sz_ls[i - 1] - K);
            }
        }
        early_sz = min(early_sz, K);
        early_sz_ls[i] = early_sz;
        for (int j = 1; j <= early_sz; ++j) {
            ans_mat[i][j] = idx;
        }
        if (early_sz != 0) {
            ++idx;
        }
    }
}

void gen_late_seg() {
    for (int i = 1; i <= N; ++i) {
        for (int j = early_sz_ls[i] + 1; j <= K; ++j) {
            ans_mat[i][j] = idx;
        }
        if (early_sz_ls[i] != K) {
            ++idx;
        }
    }
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=17137

源代码

// teamname: Gospel_rock
/**
 * Problem: 骰子大战
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1199&pid=1006
 * Created: 2026-04-06 16:32:16
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N, M, K;
    ll idx = 0;
    ll bound_win;
    vector<vector<ll> > ans_mat;
    vector<ll> early_sz_ls;

    void gen_eraly_seg() {
        for (int i = 1; i <= N; ++i) {
            ll early_sz;
            if (i == 1) {
                early_sz = K - (bound_win + K - 1) / K;
            } else {
                if (early_sz_ls[i - 1] - K == 0) {
                    early_sz = K;
                } else {
                    early_sz = (bound_win - K * K) / (early_sz_ls[i - 1] - K);
                }
            }
            early_sz = min(early_sz, K);
            early_sz_ls[i] = early_sz;
            for (int j = 1; j <= early_sz; ++j) {
                ans_mat[i][j] = idx;
            }
            if (early_sz != 0) {
                ++idx;
            }
        }
    }

    void gen_late_seg() {
        for (int i = 1; i <= N; ++i) {
            for (int j = early_sz_ls[i] + 1; j <= K; ++j) {
                ans_mat[i][j] = idx;
            }
            if (early_sz_ls[i] != K) {
                ++idx;
            }
        }
    }

    Solve() {
        cin >> N >> M >> K;
        ans_mat.resize(N + 2, vector<ll>(K + 2));
        bound_win = K * K / 2 + 1;
        early_sz_ls.resize(N + 2);
        gen_eraly_seg();
        // #ifdef LOCAL
        //         debug1d(early_sz_ls);
        // #endif
        gen_late_seg();
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= K; ++j) {
                cout << ans_mat[i][j] << " ";
            }
        }
        cout << "\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=17137

*/

心路历程（WA，TLE，MLE……）

除零错误——INTEGER_DIVIDE_BY_ZERO