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

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

输出样例：

  1. 3
  2. 10
  3. 1

要素

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

想要直接预处理所有组合的结果时间复杂度超过10^8，不可取
但是组合数是两个阶乘的除法，故可以先预处理出所有的阶乘
由于是在取模的情况下做计算，而模数p是个质数，所以可以将所有除数转换成其关于p的乘法逆元，然后做乘法

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 100010, MOD = 1000000007;
  5.     static int[] fact = new int[N], infact = new int[N];
  7.     static {
  8.         fact[0] = infact[0] = 1;
  9.         for (int i = 1; i < N; i++) {
  10.             fact[i] = (int) (1L * fact[i - 1] * i % MOD);
  11.             infact[i] = (int) (infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD);
  12.         }
  13.     }
  14.     static long qmi(long a, long b, long p) {
  15.         long res = 1;
  17.         while (b > 0) {
  18.             if ((b & 1) == 1) {
  19.                 res = res * a % p;
  20.             }
  21.             a = a * a % p;
  22.             b >>= 1;
  23.         }
  24.         return res;
  25.     }
  26.     public static void main(String[] args) {
  27.         Scanner sc = new Scanner(System.in);
  29.         int m = sc.nextInt();
  31.         while (m-- > 0) {
  32.             int a = sc.nextInt(), b = sc.nextInt();
  34.             int res = (int) (1L * fact[a] * infact[b] % MOD * infact[a - b] % MOD);
  35.             System.out.println(res);
  36.         }
  37.     }
  38. }