题目大意
LMZ有 n n n个不同的基友，他每天晚上要选 m m m个一起玩，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案 m o d 10007 \bmod 10007 mod10007的值。
有 t t t组数据。
1 ≤ t ≤ 200 , 1 ≤ m , n ≤ 200 , 000 , 000 1\leq t\leq 200,1\leq m,n\leq 200,000,000 1≤t≤200,1≤m,n≤200,000,000
题解
前置知识：lucas定理
题意即求 C n m C_n^m Cnm对 10007 10007 10007取模后的值，由 l u c a s lucas lucas定理可得
C ( n , m ) = C ( n / m o d , m / m o d ) × C ( n % m o d , m % m o d ) C(n,m)=C(n/mod,m/mod)\times C(n\% mod,m\% mod) C(n,m)=C(n/mod,m/mod)×C(n%mod,m%mod)文章来源：https://www.toymoban.com/news/detail-456803.html
先预处理出 1 1 1到 m o d − 1 mod-1 mod−1的阶乘和逆元，然后递归求解即可。文章来源地址https://www.toymoban.com/news/detail-456803.html
code
#include<bits/stdc++.h>
using namespace std;
const int N=10006,mod=10007;
int jc[N+5],ny[N+5];
int mi(int t,int v){
if(!v) return 1;
int re=mi(t,v/2);
re=re*re%mod;
if(v&1) re=re*t%mod;
return re;
}
void init(){
jc[0]=1;
for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
ny[N]=mi(jc[N],mod-2);
for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
int C(int x,int y){
if(x<y) return 0;
return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int lucas(int x,int y){
if(x<y) return 0;
if(y==0) return 1;
return lucas(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
int main()
{
int t,n,m;
init();
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
printf("%d\n",lucas(n,m));
}
return 0;
}
到了这里，关于BZOJ2982 combination（lucas定理）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
