【排列组合, 逆元】求组合数 II

题目

886. 求组合数 II - 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 10^5$

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

解题

方法一：预处理 逆元 快速幂

思路

本题相比于求组合数 I增大了 $a, b$ 的数据范围，如果依旧用递推的方式预处理肯定会爆 TLE 。

我们可以先以 $O(N)$ 的时间复杂度预处理 $1 \sim 10000$ 的阶乘 $\pmod{10^9+7}$ ，这样以来就可以直接套公式^[1]以常数的时间复杂度来求组合数了。

但是还有一个问题没有解决——公式中存在除法计算，如果先取模再相除肯定会得到错误答案，但不取模阶乘又太大根本存不下来。这时就想到了乘法逆元，它的作用是：在要除以一个数，再取模时，把除法变成乘法运算，然后再取模。 完美符合我们的需求，此时组合数计算公式就变为：

$$\mathrm{C}_n^m = n! \times (m!)^{-1} \times (n! - m!)^{-1} \pmod{10^9}$$

此外，本题中模数 $10^9 + 7$ 是一个质数，所以根据费马小定理可以利用快速幂求逆元。

注意：在计算的过程中要随时注意数据范围，不要爆 int 或者爆 long 。

时间复杂度：$O(N\log{N})$ 。

代码

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

public class Main {
    static final int N = (int) 1e5 + 10, MOD = (int) 1e9 + 7;
    static long[] fact = new long[N], infact = new long[N];
    static {
        fact[0] = 1L;
        for (int i = 1; i < N; ++i) {
            fact[i] = (fact[i - 1] * i) % MOD;
            infact[i] = qmi(fact[i], MOD - 2, MOD);
        }
    }
    
    static long qmi(long base, long exp, long mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
    
    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;
            if (a == b) System.out.println(1);
            else System.out.println(fact[a] * (infact[b] * infact[a - b] % MOD) % MOD);
        }
    }
}

用 int 数组存阶乘及阶乘逆元：

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

public class Main {
    static final int N = (int) 1e5 + 10, MOD = (int) 1e9 + 7;
    static int[] fact = new int[N], infact = new int[N];
    static {
        fact[0] = 1;
        for (int i = 1; i < N; ++i) {
            fact[i] = (int) (1L * fact[i - 1] * i % MOD);
            infact[i] = (int) qmi(fact[i], MOD - 2, MOD);
        }
    }
    
    static long qmi(long base, long exp, long mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
    
    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;
            if (a == b) System.out.println(1);
            else System.out.println(1L * fact[a] * infact[b] % MOD * infact[a - b] % MOD);
        }
    }
}

---

1. 组合数计算公式：$\mathrm{C}_n^m = \frac{n!}{m!(n-m)!}$ ↩︎