预处理

1.算法原理介绍

• 当数据范围扩大时，上面的方法一明显太慢超时，于是我们可以从另一个角度出发，我们可以先将公式 $C_a^b$ = $\frac{a!}{(a-b)!\ast b!}$中的每个部分预处理出来，即用 fact[ a ] 记录 a！，用infact[ b ] 记录b的逆元，即$b^{-1}$。
• 前置知识：快速幂求逆元
• 快速幂：用于在logk的时间内快速求$a^k$的方法。
  原理介绍：$a^k$ = $a^x$ * $a^y$ * $a^z$ … 例如$a^9$ = $a^8$ * $a^1$。我们可以发现，一个数x可以转化为二进制的形式，即我们可以用$a^1$、$a^2$、$a^4$、$a^8$…来表示出任意一个数$a^k$，快速幂代码如下所示：

  ll qmi(int a, int k, int p){
   ll res = 1;
   while(k){
       if(k & 1)   res = (ll) res * a % p;
       k >>= 1;
       a = (ll) a * a % p;
   }
   
   return res;
  }
  

• 快速幂求逆元：快速幂的一种简单应用，其中还用到了费马小定律：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

2. 实例

描述：
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤105

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N = 100010, mod = 1e9 + 7;

int n;
int fact[N], infact[N];

ll qmi(int a, int k, int p){
    ll res = 1;
    
    while(k){
        if(k & 1)   res =(ll) res * a % p;
        k >>= 1;
        a = (ll) a * a % p;
    }
    
    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;
    }
    
    cin >> n;
    while(n -- ){
        int a, b;
        cin >> a >> b;
        
        cout << (ll)fact[a] * infact[a - b] % mod * infact[b] % mod << endl;
    }
    
    return 0;
}