侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-03-22 / 0 评论 / 1 点赞 / 434 阅读 / 886 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

888. 求组合数 IV - AcWing题库


输入 a,ba, b ,求 CabC_a^b 的值。

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

输入格式

共一行,包含两个整数 aabb

输出格式

共一行,输出 CabC_a^b 的值。

数据范围

1ba50001 \le b \le a \le 5000

输入样例:

5 3

输出样例:

10

解题

方法一:高精度

思路

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

Cnm=n!m!(nm)!=i=nm+1nim!=n(n1)(nm+2)(nm+1)1×2××m\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);
    }
}

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

思路

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

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

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

阶乘的质因数分解可以用:快速计算 nn 的阶乘中因子 xx 的数量:

cnt(x)=i=1logxnnxi=nx+nx2+...+nxi,xin\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);
    }
}
1

评论区