求组合数Ⅱ
1万组数据，
1
≤
b
≤
a
≤
1
0
5
1 \le b \le a \le 10^5
1≤b≤a≤105，预处理阶乘。时间复杂度
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
C
a
b
=
a
!
(
b
−
a
)
!
b
!
C_a^b = \frac{a !}{(b - a)! b!}
Cab=(b−a)!b!a!
预处理出
i
!
i !
i!和
(
i
!
)
−
1
(i !)^{-1}
(i!)−1
f
a
c
t
[
i
]
=
i
!
m
o
d
(
1
0
9
+
7
)
i
n
f
a
c
t
[
i
]
=
(
i
!
)
−
1
fact[i] = i ! mod (10^9 + 7) \\ infact[i] = (i!)^{-1}
fact[i]=i!mod(109+7)infact[i]=(i!)−1
因此
C
a
b
=
f
a
c
t
[
a
]
×
i
n
f
a
c
t
[
b
−
a
]
×
i
n
f
a
c
t
[
b
]
C_a^b = fact[a] \times infact[b - a] \times infact[b]
Cab=fact[a]×infact[b−a]×infact[b]
题目
题目描述：
给定n组询问，每组询问给定两个整数a，b，请你输出C(a,b) mod (10^9+7)的值。
输入格式
第一行包含整数n。接下来n行，每行包含一组a和b。
输出格式
共n行，每行输出一个询问的解。
数据范围
1≤n≤100000,1≤b≤a≤10^5
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
//快速幂
int qmi(int a, int k, int p) {
int res = 1;
while(k) {
if(k & 1) res = (LL) res * a % p;
a = (LL) a * a % p;
k >>= 1;
}
return res;
}
int main() {
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++ ) {
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
int n;
scanf("%d", &n);
while(n -- ) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}