摘要
Title: 885. 求组合数 I
Tag: 组合数、递推
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

885. 求组合数 I

• 题意

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

• 思路

  适用于a,b 较小的情况，如$a, b \le 2e3$

  ---

  利用

  $$c[i][j] = c[i - 1][j] + c[i - 1][j - 1]$$

  递推出来

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-11 21:30:15
  FilePath: \ACM\Acwing\885.py
  LastEditTime: 2022-03-11 21:32:31
  '''
  
  N = 2020
  c = [[0] * N for _ in range(N)]
  MOD = int(1e9 + 7)
  
  
  def init():
      for i in range(N):
          for j in range(i + 1):
              if j == 0: c[i][j] = 1
              else: c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD
  
  
  init()
  for _ in range(int(input())):
      a, b = map(int, input().split())
      print(c[a][b])