G. 给定排列 题解

---

1. 题目重述

给定整数 $n$（$2 \le n \le 10^6$），要求构造一个长度为 $n$ 的非零整数数组 $a_1, a_2, \dots, a_n$，使得对于每个位置 $i$：

• 若 $i = 1$，新元素 $b_1 = a_2$；
• 若 $i = n$，新元素 $b_n = a_{n-1}$；
• 否则 $b_i = a_{i-1} + a_{i+1}$。

得到的数组 $b$ 必须是原数组 $a$ 的一个排列（即 $b$ 是 $a$ 的重新排列）。若存在，输出 YES 及任意一个满足条件的数组；否则输出 NO。

---

2. 思路分析

我们将数组视为一个序列，变换 $T$ 将 $a$ 映射到 $b$。题目要求 $b$ 是 $a$ 的一个排列，即变换 $T$ 相当于对 $a$ 进行了一次置换。寻找一个非零整数序列满足 $T(a) = \sigma(a)$，其中 $\sigma$ 是一个置换。

直接搜索或推导通解较困难，但观察到标程采用按 $n \bmod 6$ 的余数分类构造的方法，表明存在周期性或模块化的构造模式。

2.1 模 6 的周期性

标程中反复出现长度为 $6$ 的模块：

• 1 -1 -2 -1 1 2

以及其变体：

• -1 3 4 1 -3 -4
• 4 1 -3 -4 -1 3

这些序列有什么性质？让我们验证长度为 $6$ 的基本模块 [1, -1, -2, -1, 1, 2]。

计算每个位置的相邻和（首尾特殊）：

• 位置 1：邻居只有位置 2，$b_1 = -1$
• 位置 2：$b_2 = 1 + (-2) = -1$？等等，$1$ 和 $-2$ 的和是 $-1$，但原数组第二个元素也是 $-1$，似乎并不直接匹配。

但题目要求 $b$ 是 $a$ 的排列，即多重集相同即可，不必对应位置相同。我们需要验证该模块在某种循环连接下，整体变换后恰好得到原模块的某个排列。实际上，这些模块是通过解线性方程组或利用对称性设计出来的，保证它们在拼接后满足条件。

2.2 构造原理

我们可以将变换 $T$ 看作一个线性映射。若将 $a$ 写为列向量，则 $b = M a$，其中 $M$ 是一个三对角矩阵，主对角线为 $0$，次对角线为 $1$（两端行稍有不同）。我们要求 $b$ 是 $a$ 的排列，即存在置换矩阵 $P$ 使得 $M a = P a$，或 $(M - P)a = 0$。因此需要找一个非零向量 $a$ 满足 $(M - P)a = 0$，即 $a$ 在 $M - P$ 的零空间中。

对于特定的 $n$，我们可以尝试寻找简单的置换 $P$（如循环移位、反转等）并求解对应的齐次线性方程组，希望得到非零整数解。标程的构造即为预先找到的对于各类 $n \bmod 6$ 的特解，并利用长度为 $6$ 的模块进行扩展。

2.3 无解情况的判定

标程指出当 $n = 3$ 或 $n = 5$ 时无解，其他 $n$ 均有解。这可以通过穷举小 $n$ 或线性代数分析得出。事实上，$n=3$ 时方程组无解，$n=5$ 也无解。

---

3. 分类构造详解

以下按 $n \bmod 6$ 的余数分别说明构造方法。

3.1 $n \equiv 0 \pmod{6}$

设 $n = 6k$。构造为：

2 1 -1  (1 -1 -2 -1 1 2) 重复 k-1 次  1 -1 -2

即开头三个固定数，中间重复模块，结尾三个固定数。注意模块重复 $k-1$ 次后总长度：

• 开头 $3$ 个
• 模块长度 $6 \times (k-1)$
• 结尾 $3$ 个 总和 $3 + 6(k-1) + 3 = 6k = n$。

3.2 $n \equiv 1 \pmod{6}$

设 $n = 6k + 1$（$k \ge 1$）。构造：

-5 8 1 -3 -4  (-1 3 4 1 -3 -4) 重复 k-1 次  -2 5

验证：开头 $5$ 个数，中间模块 $6(k-1)$ 个数，结尾 $2$ 个数，总和 $5 + 6(k-1) + 2 = 6k+1 = n$。

3.3 $n \equiv 2 \pmod{6}$

设 $n = 6k + 2$（$k \ge 0$）。构造：

(1 -1 -2 -1 1 2) 重复 k 次  1 -1

注意当 $k=0$（即 $n=2$）时，直接输出 1 -1 即可。

3.4 $n \equiv 3 \pmod{6}$

$n = 3$ 时无解，输出 NO。

对于 $n = 6k + 3$ 且 $k \ge 1$（即 $n \ge 9$），构造：

2 1 1 -3 -4 -1 3  (4 1 -3 -4 -1 3) 重复 k-1 次  3 -2

开头 $7$ 个数，中间 $6(k-1)$ 个数，结尾 $2$ 个数，总和 $7 + 6(k-1) + 2 = 6k+3 = n$。

3.5 $n \equiv 4 \pmod{6}$

设 $n = 6k + 4$（$k \ge 0$）。构造：

(1 -1 -2 -1 1 2) 重复 k 次  1 -1 1 2

$k=0$ 时（$n=4$）为 1 -1 1 2，检查样例：$n=4$ 时样例输出 1 2 -2 -1，而此处给出的是 1 -1 1 2，两者不同但都是合法解。

3.6 $n \equiv 5 \pmod{6}$

$n = 5$ 时无解，输出 NO。

对于 $n = 6k + 5$ 且 $k \ge 1$（即 $n \ge 11$），构造：

-2 1 1 -3 -4 -1 3  (4 1 -3 -4 -1 3) 重复 k-1 次  2 -1 2 4

开头 $7$ 个数，中间 $6(k-1)$ 个数，结尾 $4$ 个数，总和 $7 + 6(k-1) + 4 = 6k+5 = n$。

---

4. 正确性说明

标程给出的这些常数序列是通过预计算（或数学推导）得到的，它们满足对自身进行相邻和变换后，结果与原数组构成相同。由于篇幅所限，此处不逐一验证每个模块，但可以通过简单的程序验证小规模情况下的正确性。对于大规模 $n$，由模块拼接而成，变换操作在模块边界处也经过精心设计，使得整体性质得以保持。

---

5. 时间复杂度与实现细节

• 时间复杂度：$O(n)$，只需按分类输出序列。
• 空间复杂度：$O(1)$，不需要存储整个数组。

注意输出格式：先输出 YES 或 NO，对于 YES 再输出数组，元素之间用空格分隔。

---

6. 代码（附注释）

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    if (n % 6 == 0) {
        cout << "YES\n";
        cout << "2 1 -1 ";
        for (int j = 0; j < n/6 - 1; ++j)
            cout << "1 -1 -2 -1 1 2 ";
        cout << "1 -1 -2\n";
    }
    else if (n % 6 == 1) {
        cout << "YES\n";
        cout << "-5 8 1 -3 -4 ";
        for (int j = 0; j < n/6 - 1; ++j)
            cout << "-1 3 4 1 -3 -4 ";
        cout << "-2 5\n";
    }
    else if (n % 6 == 2) {
        cout << "YES\n";
        for (int j = 0; j < n/6; ++j)
            cout << "1 -1 -2 -1 1 2 ";
        cout << "1 -1\n";
    }
    else if (n % 6 == 3) {
        if (n == 3)
            cout << "NO\n";
        else {
            cout << "YES\n";
            cout << "2 1 1 -3 -4 -1 3 ";
            for (int j = 0; j < n/6 - 1; ++j)
                cout << "4 1 -3 -4 -1 3 ";
            cout << "3 -2\n";
        }
    }
    else if (n % 6 == 4) {
        cout << "YES\n";
        for (int j = 0; j < n/6; ++j)
            cout << "1 -1 -2 -1 1 2 ";
        cout << "1 -1 1 2\n";
    }
    else if (n % 6 == 5) {
        if (n == 5)
            cout << "NO\n";
        else {
            cout << "YES\n";
            cout << "-2 1 1 -3 -4 -1 3 ";
            for (int j = 0; j < n/6 - 1; ++j)
                cout << "4 1 -3 -4 -1 3 ";
            cout << "2 -1 2 4\n";
        }
    }
    
    return 0;
}

---

7. 总结

本题看似是复杂的构造题，但通过观察数据规律，将 $n$ 按模 $6$ 分类，并预先设计好各余数对应的基础模块与首尾拼接模式，即可在 $O(n)$ 时间内完成构造。对于小规模的无解情况（$n=3,5$）需特判。该题体现了在组合构造问题中利用周期性降低复杂度的思想。