【排列组合, 高精度, 筛质数】求组合数 IV

题目

888. 求组合数 IV - AcWing题库

---

输入 $a, b$ ，求 $C_a^b$ 的值。

注意结果可能很大，需要使用高精度计算。

输入格式

共一行，包含两个整数 $a$ 和 $b$ 。

输出格式

共一行，输出 $C_a^b$ 的值。

数据范围

$1 \le b \le a \le 5000$

输入样例：

5 3

输出样例：

10

解题

方法一：高精度

思路

虽然 C++ 高精度比较麻烦，但 Java 可以导 BigInteger 包直接做。

$$\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}$$

代码

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        BigInteger b = BigInteger.valueOf(in.nextInt());
        BigInteger i = BigInteger.valueOf(a), j = BigInteger.valueOf(1);
        BigInteger c = BigInteger.valueOf(1);
        for (; j.compareTo(b) <= 0; j = j.add(BigInteger.ONE), i = i.subtract(BigInteger.ONE)) {
            c = c.multiply(i).divide(j);
        }
        System.out.println(c);
    }
}

方法二：筛质数 阶乘质因数分解 高精度乘法

思路

高精度代公式有乘有除比较麻烦，但我们可以把分子分母分别质因数分解，算出每个质因子的幂的差值后再把全部乘起来即可。

具体来说，根据公式： $\mathrm{C}_n^{m} = \frac{n!}{m!(n-m)!}$ ，我们分别把 $n!, m!, (n-m)!$ 质因数分解，对于 $1 \sim 5000$ 中的每个质数，维护 $mp[i]$ 表示： $n!$ 质因数分解后 $i$ 的次数 $-$ $m!$ 质因数分解后 $i$ 的次数 $-$ $(n - m)!$ 质因数分解后 $i$ 的次数。最后把 $mp$ 中有次数的质数按照其次数乘起来就能得到答案。

线性筛预处理 $5000$ 以内的质数。

阶乘的质因数分解可以用：快速计算 $n$ 的阶乘中因子 $x$ 的数量：

$$\begin{aligned} cnt(x) &= \sum_{i=1}^{\lfloor\log_{x}{n}\rfloor}{\lfloor\frac{n}{x^i}\rfloor} \\ &= \lfloor \frac{n}{x} \rfloor + \lfloor \frac{n}{x^2} \rfloor + ... + \lfloor \frac{n}{x^i} \rfloor, \enspace x^i \le n \end{aligned}$$

高精度这里还是用 BigInteger 包。

代码

import java.util.*;
import java.math.*;

public class Main {
    static final int N = 5000;
    static int[] primes = new int[N];
    static int cnt = 0;
    static boolean[] np = new boolean[N + 1];
    static {
        for (int x = 2; x <= N; ++x) {
            if (!np[x]) primes[cnt++] = x;
            for (int i = 0; primes[i] <= N / x; ++i) {
                np[primes[i] * x] = true;
                if (x % primes[i] == 0) break;
            }
        }
    }
    static int[] mp = new int[N + 1];
    
    static int count(int n, int p) {
        int cnt = 0;
        while (n > 0) cnt += n /= p;
        return cnt;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();
        for (int i = 0; i < cnt; ++i) {
            int p = primes[i];
            mp[p] = count(a, p) - count(b, p) - count(a - b, p);
        }
        BigInteger ans = BigInteger.valueOf(1);
        for (int i = 0; i < cnt; ++i) {
            int p = primes[i];
            BigInteger bp = BigInteger.valueOf(p);
            while (mp[p]-- > 0) ans = ans.multiply(bp);
        }
        System.out.println(ans);
    }
}