P3599 Koishi Loves Construction 题解

给定正整数 $n$ ，问：

1.是否存在一个 $1,2,...,n$ 的排列，使得所有前缀和模 $n$ 的余数两两互不相等。若是，请给出构造。

2.是否存在一个 $1,2,...,n$ 的排列，使得所有前缀积模 $n$ 的余数两两互不相等。若是，请给出构造。

先找这个序列的特点。

性质Ⅰ.考虑序列中 $n$ 的位置一定在序列之首。这是因为，如果 $n$ 不在序列之首，则它与它前一个前缀和模 $n$ 所得的余数相同。

性质Ⅱ.排列中所有数的和为 $\frac{n(n+1)}{2}$，结合性质Ⅰ，于是当 $n$ 为奇数时不合题意，下设 $n$ 为偶数。

性质Ⅲ.除去首项组成的子段，序列中任意子段和不为 $n$ 的倍数是没有两前缀和相等的充要条件。

结合以上所有特点，注意到一个合法序列为：

别问我怎么注意到的QwQ

事实上，考虑后 $n-1$ 项时，要使相邻项之和不为 $n$ 的倍数，于是令相邻两项之和为 $n-1$ 或 $n+1$，结合模 $n$ 意义下正负的对称性推广到 $(x,n-x)$ 的对称性然后大胆猜想即可（）

当然可以简单说明这个式子的正确性，只需将“相邻项之和”化为 $p+k*(n-1)$ 或 $p+k*(n+1)$ 的形式即可（$k$ 是一个系数， $p$ 为左或右端点的数）。

类似T1,我们有：

性质Ⅰ：$n$ 一定在排列的末项。

再大致判断 $n$ 的范围：

1.当 $n$ 不能被表示为某个质数的若干次方时，此时一定存在两个小于 $n$ 的正整数，使得它们的积为 $n$。那么对于这两个数在排列中后一个的前缀积模 $n$ 的余数为 $0$，不合题意。

2.当 $n=p^k$（$p$ 为质数，$k$ 为正整数）时，若 $k\geq 3$，有：

$p^{[\frac{k}{2}]}p^{[\frac{k}{2}]+1}=n$ ，$n$ 为奇数

$p^{\frac{n}{2}-1}p^{\frac{n}{2}+1}=n$，$n$ 为偶数。

同上，不合题意。

3.当 $n=p$ 时：

若 $n=2$，排列 $1,2$ 符合题意。

若 $n>2$，则 $n$ 的原根 $o$ 存在。

这是本题的重要启发。

我们分别记 $j=1,2,...,n-1$ 对应的离散对数为 $y_j$,由于 $y_j$ 与 $j$ 一一对应，且 ${y_j}={1,2,...,n-1}$，故在此基础上套用第一问的构造方式即可。

4.当 $n=p^2$ 时：

这是本人在本题唯一没有处理好的点，但对AC本题无伤大雅。

若 $n=4$，合法的序列为 $1,3,2,4$。

若 $n=9$，不存在合法的序列，于是猜想 $p>2$ 时不存在合法的序列。

由于本题是洛谷月赛的题目，不采用 $OI$ 赛制，所以可以大胆猜让评测机告诉我们答案（）事实证明我猜对了（（（（雾