求有多少 \(1 \sim n\) 的排列 \(p\) 满足对于任意 $i = 1, \dots, n $，有 \(p_i \ne i\)。
方法 1（递推）：\(D_i = (D_{i-1} + D_{i-2}) \times (i-1)\)，其中 \(D_0 = 1, \ D_1 = 0\)
第一种情况，前 \(i-1\) 位形成错排，第 \(i\) 位跟前 \(i-1\) 位里的任意一位交换。
第二种情况，有 \(i-2\) 位形成错排，第 \(i\) 位跟前 \(i-1\) 位里唯一 \(p_i = i\) 的交换。
方法 2（容斥）：\(D_n = \sum \limits_{k=0}^n (-1)^k \times C_n^k \times (n-k)!\)
可以继续简化为 \(D_n = \sum \limits_{k=0}^n (-1)^k \times \dfrac{n!}{k!(n-k)!} \times (n-k)! = n! \times \sum \limits_{k=0}^n \dfrac{(-1)^k}{k!}\)。
其中 \(n!\) 可以从 \((n-1)!\) 递推，后边的求和项也是会比算 \(D_{n-1}\) 时多一项，所以这个 \(D_n\) 的表达式也可以递推。
从 \(n\) 个位置中选出 \(m\) 个位置固定 \(a_i = i\)，其它位置进行错排。
因此答案为 \(C_n^m \times D_{n-m}\)（\(D\) 表示错排数）。
组合数使用预处理阶乘和阶乘逆元的方法求。
#include <cstdio>
const int N = 1000005;
const int MOD = 1000000007;
int d[N], f[N], g[N];
int qpow(int x, int y) {
int res = 1;
while (y > 0) {
if (y & 1) res = 1ll * res * x % MOD;
x = 1ll * x * x % MOD;
y >>= 1;
}
return res;
}
void init(int n) {
f[0] = 1; g[0] = 1;
for (int i = 1; i <= n; i++) f[i] = 1ll * f[i - 1] * i % MOD;
g[n] = qpow(f[n], MOD - 2);
for (int i = n - 1; i > 0; i--) g[i] = 1ll * g[i + 1] * (i + 1) % MOD;
d[0] = 1; d[1] = 0;
for (int i = 2; i <= n; i++) d[i] = 1ll * (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
}
int C(int n, int m) {
return 1ll * f[n] * g[m] % MOD * g[n - m] % MOD;
}
int main()
{
int t; scanf("%d", &t);
init(1000000);
for (int i = 1; i <= t; i++) {
int n, m; scanf("%d%d", &n, &m);
int ans = m > n ? 0 : 1ll * C(n, m) * d[n - m] % MOD;
printf("%d\n", ans);
}
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。