题目描述

给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤105

样例

输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

算法1

($O(nlgn)$

n是10的五次方，ab的范围

（1）此题与组合数1的不同是数据范围，如果用第一题的方式，把所有可能全部先处理出来，则是10的十次方，会超时。
用求组合数的另一个式子，即阶乘Cab=a！/b！（a-b）！
（2）因为此题有模p，有/有%,要将/变成即求逆元，因为p是一个质数，所以可以用费马小定理求逆元（此题要求出所有阶乘的逆元)
（3）因为阶乘很大，所以不能用线性求N以内的所有逆元的解法。
解法如下
void init(){ //线性求逆元 可求p（质数）以内所有整数的逆元 ，具体的逆元个数看题目
inv[1]=1;//o(n)
for(int i=2;i<N;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
}

(4)所以要用另一种方法，即递推
infact[i]=(ll)infact[i-1]*qsm(i,p-2)%p; infact[i]即i的阶乘的逆元 。（具体自己推，展开即可）

(6)用long long 是因为虽然每个infact[]%p在int范围内，但是infact[i]*qsm 两个int 会大于int
、

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5,p=1e9+7;
int fact[N];//虽然很大，但是有modp 所以定义在int范围内就可以 
int infact[N];
ll qsm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)
        res=(res%p)*(a%p)%p;
        b>>=1;
        a=(a%p)*(a%p)%p;
    }
    return res;
}
void init(){
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=fact[i-1]*i;//求i的阶乘 
        infact[i]=(long long)infact[i-1]*qsm(i,p-2)%p;//求i模p的逆元，因为p为质数，用费马小定理 
    }
}
int main(){
    init(); 
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        cout<<(ll)fact[a]*infact[b]%p*infact[a-b]%p<<endl; 
    }
    return 0; 
}