【洛谷-P3599】Koishi Loves Construction

题意

Task1：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同。若存在，请给出一种构造方案。

Task2：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。若存在，请给出一种构造方案。

测试点类型 $1$：$10$ 分，满足 $X = 1$，$1 \leq n \leq 10$。
测试点类型 $2$：$40$ 分，满足 $X = 1$，$1 \leq n \leq {10}^5$。
测试点类型 $3$：$10$ 分，满足 $X = 2$，$1 \leq n \leq 10$。
测试点类型 $4$：$40$ 分，满足 $X = 2$，$1 \leq n \leq {10}^5$。

样例输入 #1

1 1
8

样例输出 #1

2 8 7 6 5 4 3 2 1

样例输入 #2

2 1
11

样例输出 #2

2 1 2 3 5 10 6 7 4 9 8 11

题解

设序列为 $a_i$，分别讨论两个子任务。

Task1

设 $s_i=(\sum\limits_{j=1}^i a_i)\bmod n$，可以有如下发现：

1. $\forall l, r, s_l\equiv s_r\pmod n$ 当且仅当 $s_r-s_{l-1}\equiv 0\pmod n$. 因此不存在区间 $[l, r]$ 的区间和是 $n$ 的倍数。
2. 当 $a_i=n$ 时，$i=1$.
3. 若 $2\nmid n$ 且 $n\neq 1$，无解。

接下来对有解情况进行构造。

发现 $n$ 必定为偶数，要想让 $s$ 构成 $\bmod n$ 意义下的完全剩余系，考虑把所有偶数在模意义下取相反数。

也就是说，使：

注意到，所有偶数的符号为负，再加上 $n$ 变为正数后，仍为偶数，所以 $s$ 仍然满足题意。

则有 $a_i$ 的通项公式：

注意 $a_1=n\neq 0$.

Task2

设 $s_i=(\prod\limits_{j=1}^i a_i)\bmod n$，可以有如下发现：

1. $\forall l, r, s_l\equiv s_r\pmod n$ 当且仅当 $\frac{s_r}{s_{l-1}}\equiv 0\pmod n$. 因此不存在区间 $[l, r]$ 的区间积是 $n$ 的倍数。
2. 当 $a_i=n$ 时，$i=n$.
3. 当 $a_i=1$ 时，$i=1$.
4. 当 $n$ 为合数时（$4$ 除外），$n\mid (n-1)!$，所以 $s_{n-1}\equiv s_n\pmod n$，无合法方案。

因此序列开头为 $1$，末尾为 $n$，$n$ 为质数，想到 $s_i=i$ 是否可行？

下面在 $s_{i-1}+1\equiv s_i\pmod n$ 的情况下构造：

于是可以从头开始递推完成构造。