侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【排列组合, 递推】求组合数 I

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

题目

885. 求组合数 I - AcWing题库


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

输入格式

第一行包含整数 nn

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

输出格式

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

数据范围

1n100001 \le n \le 10000 ,
1ba20001 \le b \le a \le 2000

输入样例:

3
3 1
5 3
2 2

输出样例:

3
10
1

解题

方法一:递推

思路

本题询问比较多,如果对每组询问直接用公式 Cnm=n!m!(nm)!\mathrm{C}_n^m = \frac{n!}{m!(n-m)!} 求组合数的话,时间复杂度最差会到 O(10000×2000)=O(2×108)O(10000\times 2000) = O(2\times10^8) 显然会超时。

但是本题 a,ba, b 的取值范围都比较小,为 20002000 ,所以我们可以预处理 120001 \sim 2000 的所有组合数。

组合数递推式:Cnm=Cn1m+Cn1m1\mathrm{C}_n^m = \mathrm{C}_{n-1}^m + \mathrm{C}_{n-1}^{m-1}

证明:

nn 个物品中选择 mm 个物品( Cnm\mathrm{C}_n^m ),假如当前拿出来了一个物品:

  • 如果该物品不在要选择的 mm 个物品中,那么我们还需要在 n1n-1 个物品中选择 mm 个物品( Cn1m\mathrm{C}_{n-1}^{m} );
  • 如果该物品要选择的 mm 个物品中,那么我们还需要在 n1n-1 个物品中选择 m1m-1 个物品( Cn1m1\mathrm{C}_{n-1}^{m-1} )。

综上, Cnm=Cn1m+Cn1m1\mathrm{C}_n^m = \mathrm{C}_{n-1}^m + \mathrm{C}_{n-1}^{m-1} 成立。

时间复杂度:O(N2)O(N^2)

代码

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

public class Main {
    static final int N = 2000, MOD = (int) 1e9 + 7;
    static int[][] c = new int[N + 1][N + 1];
    static {
        for (int n = 0; n <= N; ++n) {
            for (int m = 0; m <= n; ++m) {
                if (m == 0) c[n][m] = 1;
                else c[n][m] = (c[n - 1][m] + c[n - 1][m - 1]) % MOD;
            }
        }
    }
    
    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;
            System.out.println(c[a][b]);
        }
    }
}
0
博主关闭了所有页面的评论