题目描述

给出两个正整数 $n, k$。你需要计算：从 $0, 1, \dots, n-1$ 这 $n$ 个整数中随机选择 $k$ 个不同的整数，组成的集合的 $\text{MEX}$ 的期望是多少？

可以证明答案为一个有理分数 $\frac{x}{y}$，你需要输出这个分数对 $10^9 + 7$ 取模后的结果。

$\text{MEX}$ 定义： 表示集合内最小的未出现的自然数。

• 例如：$\text{MEX}(1, 0, 2, 4) = 3$
• 例如：$\text{MEX}(1, 2, 3, 4) = 0$

输入格式

第一行一个正整数 $T$ ($1 \le T \le 10^4$)，表示数据组数。

对于每一组数据，输入两个正整数 $n, k$ ($1 \le k \le n \le 10^9$)。

输出格式

对于每一组数据，输出一行一个整数，表示期望 $\text{MEX}$ 对 $10^9 + 7$ 取模后的结果。

样例输入 1

1
5
2
3 2
3
10 7
4
1000 278
5
1000000 114514
6
1000000000 20250406

这道题的结论非常简洁，可以通过期望的定义和组合恒等式推导出来。

核心推导过程

1. 期望公式转换：

   对于非负整数随机变量 $X$，其期望 $E[X] = \sum_{i=1}^{\infty} P(X \ge i)$。在这里，$X$ 是集合的 MEX。

   $MEX \ge i$ 意味着整数 $0, 1, 2, \dots, i-1$ 都在你选择的 $k$ 个数中。

2. 计算概率 $P(MEX \ge i)$：

   • 总的选择方案数：从 $n$ 个数中选 $k$ 个，即 $\binom{n}{k}$。
   • 满足 $MEX \ge i$ 的方案数：由于 $0, 1, \dots, i-1$ 这 $i$ 个数必须选，剩下的 $k-i$ 个数必须从剩余的 $n-i$ 个数中选，即 $\binom{n-i}{k-i}$。
   • 因此，$P(MEX \ge i) = \frac{\binom{n-i}{k-i}}{\binom{n}{k}}$。

3. 求和计算：

   $$E[MEX] = \sum_{i=1}^{k} \frac{\binom{n-i}{k-i}}{\binom{n}{k}}$$

   注意到 $i$ 的最大值只能是 $k$（因为你总共只选了 $k$ 个数，MEX 不可能超过 $k$）。

   提取常数项：

   $$E[MEX] = \frac{1}{\binom{n}{k}} \sum_{i=1}^{k} \binom{n-i}{k-i}$$

   对求和项使用 朱世杰恒等式（Hockey-stick Identity），即

   $$\sum_{j=r}^m \binom{j}{r} = \binom{m+1}{r+1}$$

   我们将求和项倒过来看:

   $$\binom{n-k}{0} + \binom{n-k+1}{1} + \dots + \binom{n-1}{k-1}$$

   根据恒等式

   $$\sum_{i=0}^r \binom{n+i}{i} = \binom{n+r+1}{r}$$

   这里 $n$ 对应 $n-k$，$r$ 对应 $k-1$。

   求和结果为

   $$\binom{(n-k) + (k-1) + 1}{k-1} = \binom{n}{k-1}$$

4. 最终化简：

   $$E[MEX] = \frac{\binom{n}{k-1}}{\binom{n}{k}}$$

   展开组合数：

   $$\frac{n!}{(k-1)!(n-k+1)!} \times \frac{k!(n-k)!}{n!} = \frac{k!}{(k-1)!} \times \frac{(n-k)!}{(n-k+1)!} = \frac{k}{n-k+1}$$

结论

对于给定的 $n, k$，期望值为：

时间复杂度分析

• 时间复杂度：每个测试用例只需计算一次逆元，复杂度为 $O(\log MOD)$。对于 $T=10^4$ 组数据，总时间约为 $O(T \log MOD)$，完全满足 1s 的时限。
• 空间复杂度：$O(1)$。