|
Powered by:NEFU AB-IN
Link
885. 求组合数 I
-
题意
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C(a,b) mod(10^9+7) 的值。
-
思路 适用于a,b 较小的案列，如
a
,
b
≤
2
e
3
a, b \le 2e3
a,b≤2e3
利用
c
[
i
]
[
j
]
=
c
[
i
?
1
]
[
j
]
+
c
[
i
?
1
]
[
j
]
c[i][j] = c[i - 1][j] + c[i - 1][j]
c[i][j]=c[i?1][j]+c[i?1][j]
递推出来 -
代码 '''
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])
|