EasyConstruction - 题解

标签与难度

标签: 构造, 数学, 数论, 模运算, 排列 难度: 1500

题目大意喵~

主人，你好呀！这道题是这样的喵~

我们需要构造一个从 $1$ 到 $n$ 的排列 $P$（也就是 $1$ 到 $n$ 每个数字都只出现一次）。这个排列 $P$ 需要满足一个非常奇特的条件：对于从 $1$ 到 $n$ 的每一个整数 $i$，都存在一个长度为 $i$ 的连续子数组，其所有元素的和模 $n$ 等于 $k$。

如果能找到这样的排列，就把它打印出来；如果找不到，就告诉人家一声 "-1"，呐。

举个栗子：如果 $n=3, k=0$，一个可行的排列是 3 1 2。

• 长度为1：子数组 3 的和是 3， $3 \pmod 3 = 0$。
• 长度为2：子数组 1 2 的和是 3， $3 \pmod 3 = 0$。
• 长度为3：子数组 3 1 2 的和是 6， $6 \pmod 3 = 0$。 你看，每个长度都满足条件了喵！

解题思路分析

Mya~ 这道题要求对 所有 长度都满足条件，听起来就好严格哦！直接去构造一个满足这么多条件的排列，就像在毛线团里找线头一样，有点困难呢。不如我们先换个思路，看看有没有什么简单的必要条件，可以帮我们排除掉那些肯定无解的情况，喵~

一个最特别的子数组是什么呢？当然是整个排列自己啦！它的长度是 $n$。 根据题目要求，这个长度为 $n$ 的子数组（也就是整个排列）的和，模 $n$ 之后必须等于 $k$。

整个排列的和是多少呢？就是 $1+2+3+\dots+n$，用高斯求和公式就是 $\frac{n(n+1)}{2}$。 所以，我们得到了第一个，也是最关键的必要条件：

$$\frac{n(n+1)}{2} \equiv k \pmod n$$

现在，我们来分析一下这个式子，就像猫猫分析一根逗猫棒一样仔细！

情况一：当 $n$ 是奇数时

如果 $n$ 是奇数，那么 $n+1$ 就是偶数。设 $n = 2m+1$，那么 $n+1 = 2m+2$。

$$\frac{n(n+1)}{2} = \frac{n \cdot (2m+2)}{2} = n \cdot (m+1)$$

这个结果显然是 $n$ 的整数倍，所以它模 $n$ 的结果一定是 $0$！ 所以，当 $n$ 是奇数时，我们必须有 $k=0$。如果 $k$ 不是 $0$，那就不可能构造出满足条件的排列，直接输出 "-1" 就好啦，喵~

情况二：当 $n$ 是偶数时

如果 $n$ 是偶数，那么 $n+1$ 就是奇数。设 $n = 2m$。

$$\frac{n(n+1)}{2} = \frac{2m \cdot (n+1)}{2} = m \cdot (n+1) = m \cdot n + m$$

这个结果模 $n$ 之后，前面的 $m \cdot n$ 就被消掉了，只剩下 $m$。而 $m = \frac{n}{2}$。 所以，当 $n$ 是偶数时，我们必须有 $k = \frac{n}{2}$。如果 $k$ 不是 $\frac{n}{2}$，同样也是无解的，输出 "-1" 就行啦。

---

现在我们找到了必要条件，那它们是不是充分的呢？也就是说，只要满足这些条件，就一定能构造出解吗？答案是肯定的，喵！接下来就是最开心的构造环节啦！

构造方案 (当 $n$ 是奇数, $k=0$)

我们的目标是让各种长度的子数组和都能凑出 $n$ 的倍数。一个很自然的想法就是把那些加起来等于 $n$ 的数配成对，比如 $(1, n-1), (2, n-2)$ 等等。它们的和都是 $n$，模 $n$ 之后就是 $0$！

我们可以这样排列：

1. 先把 $n$ 放在最前面。
2. 然后依次放上配对的数：$(1, n-1), (2, n-2), \dots$

最终的排列 $P$ 就是： $(n, 1, n-1, 2, n-2, \dots, \frac{n-1}{2}, \frac{n+1}{2})$。

我们来验证一下这个构造为什么是对的：

• 对于任意奇数长度 $i = 2j+1$: 我们取从第 1 个数 $(n)$ 开始，长度为 $i$ 的子数组。它的和是 $n + (1+n-1) + (2+n-2) + \dots + (j+n-j) = n + j \cdot n = (j+1)n$。这个和是 $n$ 的倍数，模 $n$ 等于 $0$。完美！
• 对于任意偶数长度 $i = 2j$: 我们取从第 2 个数 $(1)$ 开始，长度为 $i$ 的子数组。它的和是 $(1+n-1) + (2+n-2) + \dots + (j+n-j) = j \cdot n$。这个和也是 $n$ 的倍数，模 $n$ 等于 $0$。也完美！

所以，这个构造满足了所有长度的要求，太棒了喵！

构造方案 (当 $n$ 是偶数, $k=n/2$)

这个情况稍微复杂一点点，因为数字 $\frac{n}{2}$ 很特殊，它没法和别人配对成 $n$（$n - \frac{n}{2} = \frac{n}{2}$）。 不过没关系，我们可以把特殊分子 $n$ 和 $\frac{n}{2}$ 放在最前面，剩下的数再像之前一样配对。

我们的排列 $P$ 就是： $(n, \frac{n}{2}, 1, n-1, 2, n-2, \dots, \frac{n}{2}-1, \frac{n}{2}+1)$。

来验证一下这个构造，我们的目标是子数组和模 $n$ 等于 $\frac{n}{2}$：

• 对于任意奇数长度 $i = 2j+1$: 我们取从第 2 个数 $(\frac{n}{2})$ 开始，长度为 $i$ 的子数组。它的和是 $\frac{n}{2} + (1+n-1) + \dots + (j+n-j) = \frac{n}{2} + j \cdot n$。模 $n$ 之后等于 $\frac{n}{2}$。成功！
• 对于任意偶数长度 $i = 2j$: 我们取从第 1 个数 $(n)$ 开始，长度为 $i$ 的子数组。它的和是 $n + \frac{n}{2} + (1+n-1) + \dots + (j-1 + n-(j-1)) = n + \frac{n}{2} + (j-1)n = j \cdot n + \frac{n}{2}$。模 $n$ 之后也等于 $\frac{n}{2}$。又成功啦！

这样，两种情况我们都找到了必胜的构造方法！现在可以愉快地写代码了，喵~

代码实现

#include <iostream>
#include <vector>
#include <numeric>

// 乐于助人的我来帮你解决问题啦，喵~
void solve() {
    int n;
    long long k; // k 可能是 n/2，所以用 long long 预防一下
    std::cin >> n >> k;

    // 首先，我们判断 n 的奇偶性，来确定 k 必须满足的条件
    if (n % 2 == 1) {
        // 当 n 是奇数时，整个排列的和是 n 的倍数
        // 所以 k 必须是 0 才有可能，否则无解
        if (k != 0) {
            std::cout << -1 << std::endl;
            return;
        }

        // 构造排列：n, 1, n-1, 2, n-2, ...
        std::cout << n;
        for (int i = 1; i <= n / 2; ++i) {
            std::cout << " " << i << " " << n - i;
        }
        std::cout << std::endl;

    } else { // n 是偶数
        // 当 n 是偶数时，整个排列的和模 n 等于 n/2
        // 所以 k 必须是 n/2 才有可能，否则无解
        if (k != n / 2) {
            std::cout << -1 << std::endl;
            return;
        }

        // 构造排列：n, n/2, 1, n-1, 2, n-2, ...
        std::cout << n << " " << n / 2;
        // 注意配对时要避开 n/2 这个已经用过的数
        for (int i = 1; i < n / 2; ++i) {
            std::cout << " " << i << " " << n - i;
        }
        std::cout << std::endl;
    }
}

int main() {
    // 为了让输入输出更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    solve();
    
    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 我们只需要进行一次判断，然后用一个循环来生成并打印这个排列。循环的次数大约是 $N/2$ 次，所以总的时间复杂度和 $N$ 是线性关系，也就是 $O(N)$。对于这道题的数据范围来说，是飞快哒！

• 空间复杂度: $O(1)$ 我们在代码里没有使用额外的数组来存储整个排列，而是直接计算并打印出来。所以，除了输入输出和几个变量占用的空间外，我们没有使用与 $N$ 成正比的额外空间，空间复杂度是常数级别的，喵~

知识点总结

• 必要条件优先: 在解决构造类问题时，先从题目最强的约束（比如所有、任意）或最特殊的情况（比如最大、最小的子集）入手，寻找解存在的必要条件，可以大大简化问题。这道题的突破口就是考虑长度为 $n$ 的子数组。
• 模运算性质: 深刻理解 $\frac{n(n+1)}{2} \pmod n$ 的性质是解题的关键。根据 $n$ 的奇偶性，这个式子会呈现出完全不同的结果，直接决定了 $k$ 的取值。
• 配对构造法: 当需要构造和为特定值的序列时，i 和 target - i 这种配对思想是非常有用的。在这道题里，target 就是 $n$，配对 $(i, n-i)$ 可以方便地构造出和为 $n$ 的倍数的子数组。
• 特殊元素处理: 当构造中出现无法配对的“特殊”元素时（比如偶数 $n$ 情况下的 $n/2$），通常将它们放在序列的开头或结尾等特殊位置，再对剩下的常规元素进行统一处理，是一种有效的策略。

希望这篇题解能帮到你，喵~ 如果还有问题，随时可以再来问我哦！