【排列组合, Lucas定理】求组合数 III

题目

887. 求组合数 III - AcWing题库

---

给定 $n$ 组询问，每组询问给定三个整数 $a, b, p$ ，其中 $p$ 是质数，请你输出 $C_a^b \bmod p$ 的值。

输入格式

第一行包含整数 $n$ 。

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

输出格式

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

数据范围

$1 \le n \le 20$ ,
$1 \le b \le a \le 10^{18}$ ,
$1 \le p \le 10^5$ ,

输入样例：

3
5 3 7
3 1 5
6 4 13

输出样例：

3
3
2

解题

方法一：Lucas 定理 逆元 快速幂

Lucas 定理

Lucas 定理内容如下：对于质数 $p$，有：

$$\mathrm{C}_{n}^{m} \equiv (\mathrm{C}_{n \bmod p}^{m \bmod p}) \cdot (\mathrm{C}_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor}) \pmod{p}$$

也就是说：

$$\mathrm{C}_{n}^{m} \bmod p = \mathrm{C}_{n \bmod p}^{m \bmod p} \cdot \mathrm{C}_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor} \bmod p$$

证明咱不会（

思路

本题询问数量很少， $a, b$ 范围特别大，且模数 $p$ 较小，适合用 Lucas 定理求解。

具体来说：

• 若 a < p \and b < p ，那么直接从定义出发，使用公式求解：

  $$\mathrm{C}_n^{m} = \frac{n!}{m!(n-m)!} = \frac{\prod_{i=n-m+1}^{n} i}{m!} = \frac{n(n-1) \dots (n - m + 2)(n - m + 1)}{1 \times 2 \times \dots \times m}$$

• 否则代入 Lucas 公式递归。

由于要取模，计算中的除法依旧和求组合数 II中一样计算除数的逆元以把除法转换为乘法。

代码

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

public class Main {
    static int p;
    
    static long qmi(long base, long exp) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) %p;
            base = (base * base) % p;
            exp >>= 1;
        }
        return res;
    }
    
    static int C(int n, int m) {
        long res = 1L;
        for (int a = n, b = 1; b <= m; --a, ++b) {
            res = res * a % p;
            res = res * qmi(b, p - 2) % p;
        }
        return (int) res;
    }
    
    static int lucas(long a, long b) {
        if (a < p && b < p) return C((int) a, (int) b);
        else return (int) (1L * C((int) (a % p), (int) (b % p)) * lucas(a / p, b / p) % p);
    }
    
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            long a = in.nextLong(), b = in.nextLong();
            p = in.nextInt();
            System.out.println(lucas(a, b));
        }
    }
}