AcWing算法基础课笔记——求组合数2

求组合数Ⅱ

1万组数据，$1\le b\le a\le 10^5$，预处理阶乘。时间复杂度$O(NlogN)$
$$C_a^b=\frac{a!}{(b-a)!b!}$$
预处理出$i!$和$(i!{)}^{-1}$
$$\begin{gathered} fact[i]=i!mod(10^9+7) \\ infact[i]=(i!{)}^{-1} \end{gathered}$$
因此
$$C_a^b=fact[a]\times infact[b-a]\times 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;
}