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;
}