Update 2025/7/25：为契合题目主题，增加文章《别样的构造大战》。

别样的构造大战

往下翻，有正常版题解。

一天，肚子的给我打来电话。他说："你敢不敢和我举行碰碰车大战？给定三个整数

n, m, k

，构造

k

个

m

元组，满足每个元素在

[1, n]

中，且任意两个元组删去任意相同位置的一对元素后，剩下的部分都不相同。"我豪爽地答应了："我当然敢！周日下午在 xx 路 xx 大厦举行，谁不来谁就是怂货。"

我原本以为我恐吓了肚子的，肚子的应该躲在机房，不敢找我，可正当这时，我听见了音乐声，原来是我洛谷私信响了，一看，竟然是肚子的发来的输入样例：3 3 3。他还真有勇气，我轻蔑一笑，准备构造

3

个

3

元组，使每个元组的每个元素都相同：

CPP

1 1 1
2 2 2
3 3 3

可正当这时，肚子的打来电话："小废物，当

k

超过

n

，你这方法不就被 hack 了？再不会正解你的锣鼓账号就要被我机惨了！"听到他对我的毒骂之后，我回击道："我要用

n

进制展开构造，前

m-1

个分量用

n

进制表示索引，最后一个分量由前

m-1

个分量的和模

n

决定，使任意两个元组至少有两个位置不同，再把你的

2147483647

个小号挂在同一场锣鼓月赛上并提交 AI 生成的代码，让你被封掉，你说好不好啊。"

他吓得没再回应我，可是到了周日，肚子的竟然又给我打电话了，他还真要和我举行构造大战，于是我按照约定，到达了 xx 大厦，可他已经等我很久了。

第一回合，我占上风，当

k \leq n

时，我直接输出

k

个元组，每个元组都是相同的数字：

CPP

for (int i = 1; i <= k; i++) {
    for (int j = 0; j < m; j++) {
        printf("%d ", i);
    }
    printf("\n");
}

肚子的还在手算

k=1 \times 10^5

的情况，他比不过我，到了第六回合，他就主动认输了。

第二回合，他开始占上风，构造出了一个

n=2, m=3, k=4

的情况。我也不甘示弱，我们僵持了

10^9+7

个回合，我由于轻敌地尝试：

CPP

// 错误示范：最后一个分量随便填
元组0: (1, 1, 1)
元组1: (1, 2, 2)
元组2: (2, 1, 2)
元组3: (2, 2, 1)

结果发现我的策略看似正确，但当

k=5

时，我无论如何都构造不出第五个元组，被他击败了。

从那时开始，我就不轻敌了，我认真研究他的套路，于是我总结出了一种方案：最后一个分量取前

m-1

个分量的和模

n

再加一，这样如果两个元组前

m-1

位只有一个位置不同，那么最后一个分量就会不同：

CPP

last = (sum(a[0] to a[m-2]) - 1) % n + 1;

第二天，我们举行第三局，他使用祖传暴力，对我发动猛烈的攻击，我们势均力敌，平分秋色，

k \times m

最大

10^6

的数据规模使我们比了

998244353

个小时，也没分出胜负。

后来，他不知不觉的睡着了，我趁着这个好机会，一记凌车漂移，一飞冲天，精准地输出了所有元组：

CPP

// 对于k>n的情况
int d = m - 1;
for (long long i = 0; i < k; i++) {
    long long temp = i;
    // 将i转换成d位的n进制数
    for (int j = d-1; j>=0; j--) {
        a[j] = temp % n + 1;  // 映射到[1,n]
        temp /= n;
    }
    long long s = 0;
    for (int j = 0; j < d; j++) s += a[j];
    long long last = (s-1) % n + 1;  // 关键操作
    
    // 输出
    for (int j = 0; j < d; j++) printf("%d ", a[j]);
    printf("%lld\n", last);
}

打的他不敢还手，对他的打击比 freopen 写成 freeopen 还大。

正常版题解

这是一道 Special Judge 题目。

题意简述

本题要求构造

k

个

m

元组，满足以下条件：

每个元素均为 $[1, n]$ 中的整数。
对于任意两个不同的元组 $i$ 和 $j$ ，以及任意位置 $p$ ，存在一个位置 $l \neq p$ 使得 $x_{i,l} \neq x_{j,l}$ （即删除任意位置 $p$ 后，剩余部分不同）。

思路

通过（~~kàn~~）观（tí）察（~~jiě~~），我们注意到：

条件 $2$ 等价于任意两个元组的汉明距离（不同位置的个数）至少为 $2$ 。若两个元组仅有 $1$ 个位置不同，则删除该位置后剩余部分相同，违反条件。
当 $k \leq n$ 时，可构造每个元组的所有分量相同（即 $(i, i, \dots, i)$ 形式），且 $i$ 互不相同。此时任意两个元组的所有位置均不同，汉明距离为 $m \geq 2$ ，满足条件。
当 $k > n$ 时（此时 $n$ 较小，因 $k \leq n^{m-1}$ 且 $k \times m \leq 10^6$ ）：
1. 将索引 $i$ （ $0$ 到 $k-1$ ）转换为 $m-1$ 位的 $n$ 进制数（每位数加 1 后映射到 $[1, n]$ ），作为元组的前 $m-1$ 个分量。
2. 第 $m$ 个分量取前 $m-1$ 个分量的和减 1 模 $n$ 再加 1，即 $(s - 1) \bmod n + 1$ （ $s$ 为分量和）。该操作确保若前 $m-1$ 个分量仅有一处不同，则第 $m$ 个分量不同（汉明距离至少为 $2$ ）。

Steps

当 $k \leq n$ 时：
- 输出 $k$ 个元组，第 $i$ 个元组所有分量为 $i$ 。
当 $k > n$ 时：
- 初始化 $d = m - 1$ 。
- 对每个索引 $i \in [0, k-1]$ $i \in [0, k - 1]$ ：
  - 将 $i$ 转换为 $d$ 位 $n$ 进制数（每位数加 $1$ 存储）。
  - 计算前 $d$ 个分量的和 $s$ 。
  - 第 $m$ 个分量为 $(s - 1) \bmod n + 1$ 。
  - 输出整个元组。

Code

CPP

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    long long n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
    // k <= n 时：输出所有分量相同的元组
    if (k <= n) {
        for (int i = 1; i <= k; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j > 0) {
                    printf(" ");
                }
                printf("%d", i);
            }
            printf("\n");
        }
    }
    // k > n 时：使用 n 进制展开构造
    else {
        int d = sc<int>(m - 1);  // 前 m-1 个分量
        static int a[100000];
        for (long long i = 0; i < k; ++i) {
            long long temp = i;
            // 将 i 转换为 n 进制（d 位），存储到 a（高位在前）
            for (int j = d - 1; j >= 0; --j) {
                a[j] = sc<int>(temp % n) + 1;  // 映射到 [1, n]
                temp = temp / n;
            }
            // 计算前 d 个分量的和
            long long s = 0;
            for (int j = 0; j < d; ++j) {
                s += a[j];
            }
            // 计算最后一个分量：(s-1) mod n + 1
            long long last = (s - 1) % n + 1;
            if (last == 0) {  // 确保在 [1, n] 范围内
                last = n;
            }
            // 输出元组
            for (int j = 0; j < d; ++j) {
                printf("%d ", a[j]);
            }
            printf("%lld\n", last);
        }
    }
    return 0;
}

时间复杂度为

O(k \times m)

，足以通过本题。（题目限制

k \times m \leq 10^6

）

题解：P12606 碰碰车大战

文章操作