【题解】「BZOJ2982」combination（Lucas定理求组合数）

【题目描述】
LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有 $10007$ 天，所以他想知道答案 $mod \ 10007$的值。 $(1<=m<=n<=200,000,000)$
【输入】
第一行一个整数 $t$ ，表示有t组数据。 $(t<=200)$
接下来t行每行两个整数 $n, m，$ 如题意。
【输出】
T行，每行一个数，为 $C(n, m) \ mod \ 10007$的答案。

【参考程序】

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
const int P=10007;
int jc[N],jc_inv[N];//jc[i]保存i!%p，jc_inv[i]保存i!%p的逆元
int KSM(int x,int k)
{int ans=1;while(k){if(k&1)	ans=(ans*x)%P;k>>=1;x=(x*x)%P;}return ans%P;
}
//组合数C(n,m)=n!/(m!*(n-m)!)，除法取模需要求逆元
//看作n!*(m!的逆元)*(n-m)!的逆元再取模 
int C(int n,int m)	 
{return jc[n]*jc_inv[m]%P*jc_inv[n-m]%P;
}
int Lucas(int x,int y)
{if(!y) return 1; if(x<y) return 0;if(x<P&&y<P)	return C(x,y);return (Lucas(x%P,y%P)*Lucas(x/P,y/P))%P;
}
int main()  
{  jc[0]=jc_inv[0]=1;	//特殊的C(i,0)，设定jc_inv[0]=1 for(int i=1;i<10007;i++)		//预处理 {jc[i]=(jc[i-1]*i)%P;jc_inv[i]=KSM(jc[i],P-2);	//费马小定理求逆元 }int n;scanf("%d",&n);int x,y;while(n--){scanf("%d%d",&x,&y);cout<<Lucas(x,y)<<endl;}return 0;  
}