CF487C Prefix Product Sequence 做题记录

构造 $n$ 的排列，使得其前缀积在 $mod\,n$ 意义下两两不同。

$1 \leq n \leq 10^5$。

首先显然 $1$ 放最前面，$n$ 放最后面。并且若 $n>4$ 且 $n$ 为合数就一定无解，因为 $n$ 的所有因数都会出现，所以前缀积至少会出现两个 $0$。

那么特判掉 $n\le 4$ 的情况，考虑 $n>4$ 且 $n$ 为质数的情况。

发现原排列似乎不是很好处理，于是考虑前缀积序列，考虑构造形如 $[1,2,3,4,5,\dots,n-1,0]$ 这样的前缀积序列，显然原序列一定是这个序列的差商，即 $[1,\frac{2}{1},\frac{3}{2}.\frac{4}{3},\dots,\frac{n-1}{n-2},n]$ 这样的。容易发现中间的分数显然和首尾两个数不同，并且中间的分数都是形如 $\frac{x}{x-1}$ 这样的，统统减去 $1$ 之后变成了 $\frac{1}{x-1}$，也两两不同，所以整个序列是排列，这样构造合法。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

int n,ans[S];

inline bool chk(int n)
{
	for(int i=2;i<=n-1;i++) if(n%i==0) return false;
	return true;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%n) res=(y&1)?1ll*res*x%n:res;
	return res;
}

int main()
{
	scanf("%d",&n);
	if(n==1) puts("YES\n1");
	else if(n==2) puts("YES\n1\n2");
	else if(n==3) puts("YES\n1\n2\n3");
	else if(n==4) puts("YES\n1\n3\n2\n4");
	else if(!chk(n)) puts("NO");
	else
	{
		ans[1]=1,ans[n]=n;
		for(int i=2;i<=n-1;i++) ans[i]=1ll*i*qpow(i-1,n-2)%n;
		puts("YES");
		for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	}
	return 0;
}