885. 求组合数 I
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 1. 预处理所有数据 - 图1 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000
1≤b≤a≤2000
输入样例：

  1. 3
  2. 3 1
  3. 5 3
  4. 2 2

输出样例：

  1. 3
  2. 10
  3. 1

要素

  • 10000组数据
  • 1 <= b <= a <= 2000
  • p = 1e9 + 7

直接用递推方法得出所有可能被询问的组合数结果，即杨辉三角
1. 预处理所有数据 - 图2
时间复杂度O(n2)

  1. import java.util.*;
  3. public class Main {
  4.     static final int MOD = 1000000007;
  5.     static int n = 2010;
  6.     static int[][] c = new int[n][n];
  7.     static {
  8.         for (int i = 0; i < n; i++) {
  9.             for (int j = 0; j <= i; j++) {
  10.                 if (j == 0) c[i][j] = 1;
  11.                 else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
  12.             }
  13.         }
  14.     }
  15.     public static void main(String[] args) {
  16.         Scanner sc = new Scanner(System.in);
  18.         int m = sc.nextInt();
  20.         while (m-- > 0) {
  21.             int a = sc.nextInt(), b = sc.nextInt();
  22.             System.out.println(c[a][b]);
  23.         }
  24.     }
  25. }