神仙构造题。
$\text{Luogu}$ ：https://www.luogu.com.cn/problem/P3599
$\text{CodeForces}$ ：
https://www.luogu.com.cn/problem/CF487C & http://codeforces.com/problemset/problem/487/C
比较神仙的构造题，构造前缀和和前缀积。
首先考虑前缀和，因为要求的是 $1\sim n$ 的全排列，然后就硬造，考虑构造一个前缀和的全排列，然后用差分求出。
首先，要知道：单位元需要放在第一个，这里的单位元指的是加上或者乘上这个数的时候，前后取模 $n$ 之后结果不变。很明显，前缀和的单位元为 $n$ ，前缀积的单位元是 $1$ 。随便暴力构造全排列，时间复杂度 $\mathcal O(n!)$ ，然后会得到一个通解：就会发现，前缀和有解有且仅当 $n=1$ 或 $n\equiv 0\pmod 2$ ，且有一组解为 $n,1,n-2,3,n-4,5,\cdots ,n-1$ ，即奇位上升序列和偶位下降序列的交叉序列，然后上去过后，$X=1$ 就解决了。
然后考虑前缀积，如果是满足小数的话，很容易构造出一个解为 $1,\frac{2}{1},\frac{3}{2},\frac{4}{3},\cdots,\frac{n-1}{n-2},\frac{n}{n-1}$ ，结束，可惜的是，求的是全排列，所以联想到——逆元。用费马小定理求逆元即可。
但是，我们考虑何时有解，就会发现 $n$ 是质数的时候有解，否则一定存在 $p_1\times p_2=n,1<p_1,p_2<n$ ，这样会导致提前进入取模为 $0$ 的情况。但是，是不是真的合数就没有解了呢，我们稍微考虑一下，发现 $1,4$ 有解，特判即可。至于为什么要特判，是因为费马小定理合法当且仅当模数为质数，而当 $n=4$ 的时候，逆元失效。
时间复杂度 $\mathcal O(n\log n)$ 。
$\text{CodeForces}$ 上的就是前缀积，输出格式不太一样（虽然对于构造题而言，因为有 $\text{Spj}$ 所以格式不太重要）。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(char c)
{
putchar(c);
}
template<>
inline void write(char *s)
{
while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
x=x<y?x:y;
}
const int MAXN=1e5+10;
int X,T,N;
int pri[MAXN],Tot;
bool is[MAXN];
inline int qPow(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p;b>>=1;
}
return res;
}
inline void sieve(int n)
{
is[1]=1;
for(int i=2;i<=n;++i)
{
if(!is[i]) pri[++Tot]=i;
for(int j=1;i*pri[j]<=n&&j<=Tot;++j)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
int main()
{
read(X,T);
sieve(MAXN-10);
while(T--)
{
read(N);
if(N==1)
{
puts("2 1");
continue;
}
if(X==1)
{
if(N&1) puts("0");
else
{
write("2 ");
for(int i=1;i<N;++i) write((i&1)?N-i+1:i-1,' ');
write(N-1,'\n');
}
}
else
{
if(N==4) puts("2 1 3 2 4");
else if(!is[N])
{
write("2 1 ");
for(int i=2;i<N;++i) write(1ll*i*qPow(i-1,N-2,N)%N,' ');
write(N,'\n');
}
else puts("0");
}
}
return 0;
}
|