企业网站建设用语,商贸营销型网站案例,易优cms和织梦cms的区别,手机开发商4517: [Sdoi2016]排列计数 Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 637 Solved: 396[Submit][Status][Discuss]Description 求有多少种长度为 n 的序列 A#xff0c;满足以下条件#xff1a;1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为 i#x… 4517: [Sdoi2016]排列计数 Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 637 Solved: 396[Submit][Status][Discuss] Description 求有多少种长度为 n 的序列 A满足以下条件 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多序列数对 10^97 取模。 Input 第一行一个数 T表示有 T 组数据。 接下来 T 行每行两个整数 n、m。 T500000n≤1000000m≤1000000 Output 输出 T 行每行一个数表示求出的序列数 Sample Input 5 1 0 1 1 5 2 100 50 10000 5000 Sample Output 0 1 20 578028887 60695423 HINT Source 鸣谢Menci上传 答案为C(n,m)*f[n-m]f[n-m]表示(n-m)个数错排的方案数。 错排问题戳这里 Fn(n-1)(Fn-1Fn-2) 预处理即可。 1 #includebits/stdc.h2 #define LL long long3 const int oo 0x3f3f3f3f;4 template class T inline bool Chkmin(T x, T y) { return x y ? x y, true : false; }5 template class T inline bool Chkmax(T x, T y) { return x y ? x y, true : false; }6 template class T inline T read(T x)7 {8 static int f;9 static char c;
10 for (f 1; !isdigit(c getchar()); ) if (c -) f -f;
11 for (x 0; isdigit(c); c getchar()) x x * 10 c - 48;
12 return x * f;
13 }
14 template class T inline void write(T x, char P 0)
15 {
16 static char s[20];
17 static int top 0;
18 if (x 0) x -x, putchar(-);
19 do {s[top] x % 10 48;} while (x / 10);
20 do {putchar(s[top]);} while (--top);
21 if (P) putchar(P);
22 }
23
24 static const int MAXN 1e6;
25 static const int MO 1e9 7;
26
27 static int T, N, M;
28 static int Jc[MAXN 5], Ni[MAXN 5], f[MAXN 5];
29
30 inline int Qpow(int x, int n)
31 {
32 int ans 1;
33 while (n) {
34 if (n 1) ans (LL) ans * x % MO;
35 x (LL) x * x % MO;
36 n 1;
37 }
38 return ans;
39 }
40
41 int main()
42 {
43 Ni[0] Jc[0] 1;
44 for (register int i 1; i MAXN; i) {
45 Jc[i] (LL) Jc[i - 1] * i % MO;
46 Ni[i] Qpow(Jc[i], MO - 2);
47 }
48 f[0] 1; f[1] 0;
49 for (register int i 2; i MAXN; i) {
50 f[i] (LL) (f[i - 1] f[i - 2]) * (i - 1) % MO;
51 }
52 for (read(T); T--; ) {
53 read(N), read(M);
54 write((LL) Jc[N] * Ni[N - M] % MO * Ni[M] % MO * f[N - M] % MO, \n);
55 }
56 return 0;
57 } View Code 转载于:https://www.cnblogs.com/jszyxw/p/5508409.html
