P3599 Koishi Loves Construction 题解

· · 题解

一道超级棒超级棒的题！

问题重述

给定正整数 n ，问：

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

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

T1 判断并构造

先找这个序列的特点。

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

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

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

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

n,1,n-2,3,n-4,5,n-6...

别问我怎么注意到的QwQ

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

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

T2 判断并构造

类似T1,我们有：

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

再大致判断 n 的范围：

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

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

$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$ 赛制，所以可以大胆猜让评测机告诉我们答案（）事实证明我猜对了（（（（雾