題目鏈接

---

\(Description\)

對于一個序列\(a_i\)，定義其前綴積序列為\(a_1\ \mathbb{mod}\ n,\ (a_1a_2)\ \mathbb{mod}\ n,...,(a_1a_2...a_n)\ \mathbb{mod}\ n\)。
給定\(n\)，求一個\(n\)的排列，使得該排列的前綴積序列是\([0,1,2,...,n-1]\)的一個排列。無解輸出\(NO\)。
\(n\leq10^5\)。

\(Solution\)

考慮無解的情況。因為\(n!\equiv0\ (\mathbb{mod}\ n)\)，所以\((n-1)\not\equiv0\ (\mathbb{mod}\ n)\)。
\(n\)為質(zhì)數(shù)顯然可以滿足。否則設(shè)\(n=pq\)。
若\(p\neq q\)，那么有\((n-1)!\equiv0\ (\mathbb{mod}\ n)\)，GG了。
若\(p=q\)，當(dāng)\(n>4\)時，\(2p<n\)，所以也有\((n-1)!\equiv0\ (\mathbb{mod}\ n)\)，GG。
所以\(n\)為大于\(4\)的合數(shù)時無解。特判一下\(n=4\)。

首先\(a_1\)要填\(1\)，\(a_n\)要填\(n\)。
考慮能不能直接讓前綴積序列變成\(1,2,...,0\)。那么\(a_i=\frac{i}{i-1}\ \mathbb{mod}\ n,\ i>1\)。
只需要判斷是否有\(\frac{a}{a-1}=\frac{b}{b-1},\ 1\lt a\neq b\lt n\)。
稍微化一下，\(\frac{a}{a-1}=1+\frac1a,\ \frac{b}{b-1}=1+\frac1b\)，而我們知道每個數(shù)的逆元是唯一的，所以這么做就OK啦。

---

//46ms  600KB
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int N=1e5+5;int A[N],inv[N];bool IsPrime(int x)
{int t=0;for(int i=2; x!=1; ++i)while(!(x%i)){x/=i;if(++t>1) return 0;}return 1;
}int main()
{int n; scanf("%d",&n);if(n==4) return printf("YES\n1\n3\n2\n4\n"),0;if(!IsPrime(n)) return puts("NO"),0;A[1]=1, A[n]=n, inv[1]=1;for(int i=2; i<n; ++i) inv[i]=1ll*(n-n/i)*inv[n%i]%n, A[i]=1ll*i*inv[i-1]%n;puts("YES");for(int i=1; i<=n; ++i) printf("%d\n",A[i]);return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/10518469.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces.487C.Prefix Product Sequence(构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。