稳定排列计数

题目描述

求有多少种长度为 $n$ 的序列 $A$，满足以下条件：

1. $1 \sim n$ 这 $n$ 个数在序列中各出现了一次（即 $A$ 是 $1$ 到 $n$ 的一个排列）
2. 若第 $i$ 个数 $A[i]$ 的值为 $i$，则称 $i$ 是稳定的
3. 序列恰好有 $m$ 个数是稳定的

由于满足条件的序列可能很多，所以请你将序列数对 $10^9+7$ 取模后输出。

输入格式

第一行一个数 $T$，表示有 $T$ 组数据。

接下来 $T$ 行，每行两个整数 $n, m$。

输出格式

输出 $T$ 行，每行一个整数，表示求出的序列数对 $10^9+7$ 取模后的值。

数据范围

• $T \leq 500000$
• $n \leq 1000000$
• $m \leq 1000000$

输入样例

5
1 0
1 1
5 2
100 50
10000 5000

输出样例

0
1
20
578028887
60695423

样例解释

第一个测试：$n=1, m=0$

• 只有 1 个数的排列：$[1]$
• 稳定位置：位置1的值是1，所以有1个稳定位置
• 要求恰好0个稳定位置，不可能
• 输出：0

第二个测试：$n=1, m=1$

• 排列：$[1]$
• 稳定位置：1个
• 要求恰好1个稳定位置，符合
• 输出：1

第三个测试：$n=5, m=2$

• 需要计算：从5个位置中选出2个作为稳定位置，其余3个位置都不能是稳定的（即错排）
• 公式：$C(5, 2) \times D(3)$
  • $C(5, 2) = 10$（组合数）
  • $D(3) = 2$（3个元素的错排数：2种）
  • 总数：$10 \times 2 = 20$
• 输出：20

第四、五个测试：大数计算

• 需要模 $10^9+7$ 计算
• 输出取模后的结果

问题分析

这个问题是带有指定数量不动点的排列计数问题。

关键概念

1. 排列：$1 \sim n$ 每个数恰好出现一次
2. 稳定位置（不动点）：$A[i] = i$ 的位置 $i$
3. 错排：没有稳定位置的排列

计算公式

要求恰好有 $m$ 个稳定位置的排列数：

1. 从 $n$ 个位置中选出 $m$ 个作为稳定位置：$C(n, m)$
2. 剩下的 $n-m$ 个位置必须形成错排（没有任何位置是稳定的）：$D(n-m)$

因此，总数为：

$$\text{Answer}(n, m) = C(n, m) \times D(n-m)$$

其中：

• $C(n, m)$ 是组合数
• $D(k)$ 是 $k$ 个元素的错排数

错排数公式

$k$ 个元素的错排数 $D(k)$ 有递推公式：

$$D(k) = (k-1) \times [D(k-1) + D(k-2)]$$

边界条件：

• $D(0) = 1$（空排列算一种错排）
• $D(1) = 0$（1个元素不可能错排）

组合数计算

组合数 $C(n, m)$ 需要模 $10^9+7$ 计算：

$$C(n, m) = \frac{n!}{m!(n-m)!} \pmod{10^9+7}$$

由于 $10^9+7$ 是质数，可以使用阶乘逆元预处理。

算法设计

考虑到数据范围：

• $T$ 最多 500,000 组查询
• $n, m$ 最多 1,000,000

需要预处理：

1. 阶乘数组 fact[i] = i! mod MOD
2. 阶乘逆元数组 inv_fact[i] = (i!)^{-1} mod MOD
3. 错排数组 derange[i] = D(i) mod MOD

然后对于每组查询 $(n, m)$：

• 如果 $m > n$，答案为 0
• 否则，答案为 C(n, m) * derange[n-m] mod MOD

特殊情况

• 当 $n = m$ 时：$D(0) = 1$，所以答案是 $C(n, n) = 1$
• 当 $m = 0$ 时：答案就是错排数 $D(n)$
• 当 $m < 0$ 或 $m > n$ 时：答案为 0

时空限制

• 时间限制：2秒
• 空间限制：256MB