BZOJ 2982 combination Lucas定理

Description

LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)

Input

  第一行一个整数t，表示有t组数据。(t<=200)

  接下来t行每行两个整数n, m，如题意。

Output

T行，每行一个数，为C(n, m) mod 10007的答案。

Sample Input

4

5 1

5 2

7 3

4 2

Sample Output

5

10

35

6

HINT

​​传送门​​

终于会lucas了= =

要求C(n,m)%p，其中p是一个质数，那么lucas定理就是给了这么一个式子：

C(n,m)=C(n%p,m%p)*C(n/p,m/p)%p

当n<m返回0，当n<p且m<p返回C(n,m)%p（即直接计算）即可。

预处理阶乘以及逆元，然后递归解决即可。

#include<bits/stdc++.h>
using namespace std;
const int
    Mod=10007;
int inv[Mod],fac[Mod];
void Pre(){
    inv[0]=inv[1]=fac[0]=1;
    for (int i=1;i<Mod;i++) fac[i]=fac[i-1]*i%Mod;
    for (int i=2;i<Mod;i++)
        inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
    for (int i=2;i<Mod;i++)
        inv[i]=inv[i-1]*inv[i]%Mod;
}
int C(int n,int m){
    return fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int Lucas(int n,int m){
    if (n<m) return 0;
    if (n<Mod && m<Mod) return C(n,m);
    return Lucas(n%Mod,m%Mod)*Lucas(n/Mod,m/Mod)%Mod;
}
int main(){
    Pre();
    int cas,n,m;
    scanf("%d",&cas);
    while (cas--){
        scanf("%d%d",&n,&m);
        printf("%d\n",Lucas(n,m));
    }
    return 0;
}