侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

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

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

题目

886. 求组合数 II - AcWing题库


给定 nn 组询问,每组询问给定两个整数 aba,b ,请你输出 Cabmod(109+7)C_a^b \bmod (10^9 + 7) 的值。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含一组 aabb

输出格式

nn 行,每行输出一个询问的解。

数据范围

1n100001 \le n \le 10000 ,
1ba1051 \le b \le a \le 10^5

输入样例:

3
3 1
5 3
2 2

输出样例:

3
10
1

解题

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

思路

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

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

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

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

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

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

时间复杂度:O(NlogN)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. 组合数计算公式:Cnm=n!m!(nm)!\mathrm{C}_n^m = \frac{n!}{m!(n-m)!} ↩︎

0
博主关闭了所有页面的评论