【排列组合, 递推】求组合数 I

题目

885. 求组合数 I - AcWing题库

---

给定 $n$ 组询问，每组询问给定两个整数 $a，b$ ，请你输出 $C_a^b \bmod (10^9 + 7)$ 的值。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含一组 $a$ 和 $b$ 。

输出格式

共 $n$ 行，每行输出一个询问的解。

数据范围

$1 \le n \le 10000$ ,
$1 \le b \le a \le 2000$

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

解题

方法一：递推

思路

本题询问比较多，如果对每组询问直接用公式 $\mathrm{C}_n^m = \frac{n!}{m!(n-m)!}$ 求组合数的话，时间复杂度最差会到 $O(10000\times 2000) = O(2\times10^8)$ 显然会超时。

但是本题 $a, b$ 的取值范围都比较小，为 $2000$ ，所以我们可以预处理 $1 \sim 2000$ 的所有组合数。

组合数递推式：$\mathrm{C}_n^m = \mathrm{C}_{n-1}^m + \mathrm{C}_{n-1}^{m-1}$ 。

证明：

在 $n$ 个物品中选择 $m$ 个物品（ $\mathrm{C}_n^m$ ），假如当前拿出来了一个物品：

• 如果该物品不在要选择的 $m$ 个物品中，那么我们还需要在 $n-1$ 个物品中选择 $m$ 个物品（ $\mathrm{C}_{n-1}^{m}$ ）；
• 如果该物品在要选择的 $m$ 个物品中，那么我们还需要在 $n-1$ 个物品中选择 $m-1$ 个物品（ $\mathrm{C}_{n-1}^{m-1}$ ）。

综上， $\mathrm{C}_n^m = \mathrm{C}_{n-1}^m + \mathrm{C}_{n-1}^{m-1}$ 成立。

时间复杂度：$O(N^2)$

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 2000, MOD = (int) 1e9 + 7;
    static int[][] c = new int[N + 1][N + 1];
    static {
        for (int n = 0; n <= N; ++n) {
            for (int m = 0; m <= n; ++m) {
                if (m == 0) c[n][m] = 1;
                else c[n][m] = (c[n - 1][m] + c[n - 1][m - 1]) % MOD;
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            System.out.println(c[a][b]);
        }
    }
}