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