CF1391C-Cyclic Permutations
题目:
题目描述:
A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array) and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).
Consider a permutation $ p $ of length $ n $ , we build a graph of size $ n $ using it as follows:
- For every $ 1 \leq i \leq n $ , find the largest $ j $ such that $ 1 \leq j < i $ and $ p_j > p_i $ , and add an undirected edge between node $ i $ and node $ j $
- For every $ 1 \leq i \leq n $ , find the smallest $ j $ such that $ i < j \leq n $ and $ p_j > p_i $ , and add an undirected edge between node $ i $ and node $ j $
In cases where no such $ j $ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.
For clarity, consider as an example $ n = 4 $ , and $ p = [3,1,4,2] $ ; here, the edges of the graph are $ (1,3),(2,1),(2,3),(4,3) $ .
A permutation $ p $ is cyclic if the graph built using $ p $ has at least one simple cycle.
Given $ n $ , find the number of cyclic permutations of length $ n $ . Since the number may be very large, output it modulo $ 10^9+7 $ .
Please refer to the Notes section for the formal definition of a simple cycle
输入格式:
The first and only line contains a single integer $ n $ ( $ 3 \le n \le 10^6 $ ).
输出格式:
Output a single integer $ 0 \leq x < 10^9+7 $ , the number of cyclic permutations of length $ n $ modulo $ 10^9+7 $ .
样例:
样例输入 1:
样例输出 1:
样例输入 2:
样例输出 2:
思路:
实现:
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
| /*
*User: ybw051114
*Time: 2020.08.09 22:35:06
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
const long long mod = 1e9 + 7;
long long ksm(long long a, int n)
{
long long ans = 1;
while (n)
{
if (n & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
int main()
{
long long n;
yin >> n;
long long ans = 1;
for (long long i = 1; i <= n; i++)
{
ans *= i;
ans %= mod;
}
yout << (ans - ksm(2, n - 1) + mod) % mod << endl;
return 0;
}
|