摘要
Title: 886. 求组合数 II
Tag: 组合数、阶乘
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

886. 求组合数 II

• 题意

  给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C(a, b) mod (10^9+7) 的值。

• 思路

  适用于a,b 比较大的情况，如$a, b \le 1e5$

  ---

  预先处理阶乘和阶乘的逆元即可

  $$C(a, b) = \frac {a!} {b! (a - b)!}$$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-12 10:55:10
  FilePath: \ACM\Acwing\886.py
  LastEditTime: 2022-03-12 10:55:11
  '''
  N = int(1e5 + 10)
  MOD = int(1e9 + 7)
  fact, infact = [0] * N, [0] * N
  
  fact[0] = infact[0] = 1
  for i in range(1, N):
      fact[i] = fact[i - 1] * i % MOD
      infact[i] = infact[i - 1] * pow(i, MOD - 2, MOD) % MOD
  
  for i in range(int(input())):
      a, b = map(int, input().split())
      print(fact[a] * infact[b] * infact[a - b] % MOD)