题目链接：LOJ 2034
$n$个位置中恰好有$m$个位置是稳定的，即固定$m$个位置，此时有$n \choose m$种方案；对于剩下的$n – m$个位置，满足$A_i \neq i$，即是$n – m$的错位排列，有$d(n – m)$种。
根据分步计数原理，总共有${n \choose m} \cdot d(n – m)$种方案。
这里的错排方案函数$d(x)$很好处理，使用$d(x) = (x – 1) [d(x-1) + d(x-2)]$进行递推，当然这里要记得特殊处理$d(0) = 1$。在处理$n \choose m$的时候，我们可以先处理出$[1, \max \{ n \}]$内每个数字的阶乘，然后使用
$${n \choose m} = \frac{n!}{m!(n-m)!}$$
使用乘法逆元处理除法，由于这里的$p$为质数，$a$在模$p$意义下的乘法逆元等于$a^{p-2} \bmod p$。
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 1000000 + 5; const LL p = (LL)(1E9) + 7; LL T, n, m; LL f[maxn], d[maxn]; LL getPow(LL x, LL y) { LL ret = 1; while (y) { if (y & 1) ret = ret * x % p; x = x * x % p; y >>= 1; } return ret; } void getF() { f[0] = 1; for (LL i = 1; i < maxn; ++i) f[i] = f[i - 1] * i % p; } void getD() { d[0] = 1; d[1] = 0; d[2] = 1; for (LL i = 3; i < maxn; ++i) d[i] = ((i - 1) * (d[i - 1] + d[i - 2])) % p; } int main() { scanf("%lld", &T); getF(), getD(); for (LL cs = 1; cs <= T; ++cs) { scanf("%lld%lld", &n, &m); LL ans = d[n - m]; ans = ans * f[n] % p; ans = ans * getPow(f[m], p - 2) % p; ans = ans * getPow(f[n - m], p - 2) % p; printf("%lld\n", ans); } return 0; } |
[…] LOJ 2034 – 「SDOI 2016」排列计数 […]