Description
有T个询问，每个询问给出n、m，求1-n所有的排列中，恰好有m个位置满足P_i=i的排列个数。
( T<=500000, n<=1000000, m<=1000000. )
Solution
Key：错排，逆元。
错排就是指将1-n这n个数放入标号为1-n的袋子中，全部装错的情况种数。
设\(F_n\)表示这个东西，那么考虑将n放到k的位置上，如果k放到了n的位置，那么剩下n-2个元素，就是\(F_{n-2}\)，如果k不放到n的位置上，那么剩下n-1个元素，就是\(F_{n-1}\)，根据加法原理总结最后的公式：
\[F_n=(n-1)*(F_{n-1}+F_{n-2})\]数a的逆元就是指在模p意义下满足\(a*x\equiv 1 \pmod {p}\)的最小的x。
设m的逆元为k，那么求n/m在模p意义下的值时就可以求n*k。
然后说这道题，我们先从n个元素中挑出m个来让他们的P_i=i，然后将n-m个错排即可。答案为：\((_m^n)*F_{n-m}\)。
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
LL F[1000005], Frac[1000005], Fran[1000005];
const LL mod = 1000000007;
const LL moe = 1000000005;
int n, m;
LL ksm(LL a, LL b) {
LL ret = 1, tmp = a;
while (b) {
if (b & 1) ret = (ret * tmp) % mod;
tmp = (tmp * tmp) % mod;
b >>= 1;
}
return ret;
}
LL C(int n, int m) {
return Frac[n] * Fran[m] % mod * Fran[n-m] % mod;
}
void init() {
F[0] = 1; F[1] = 0; F[2] = 1; Frac[0] = 1; Fran[0] = 1;
for (int i = 1; i <= 1000000; ++i) Frac[i] = Frac[i-1] * i % mod;
for (int i = 1; i <= 1000000; ++i) Fran[i] = ksm(Frac[i], moe);
for (int i = 3; i <= 1000000; ++i) F[i] = (F[i-1] + F[i-2]) % mod * (i-1) % mod;
}
int main() {
init();
int T = getint();
while (T--) {
n = getint(); m = getint();
if (m > n) {
printf("0\n");
} else {
LL ans = (C(n, m) * F[n-m]) % mod;
printf("%lld\n", ans);
}
}
return 0;
}
|