排列组合
Lucas定理模板题……
感觉我做题顺序有点问题啊……应该是BZOJ 2982-->HDOJ 3037-->BZOJ 1272
好吧这个现在来看就有些水了……
预处理一下fact和inv即可
/**************************************************************
Problem: 2982
User: Tunix
Language: C++
Result: Accepted
Time:4 ms
Memory:1352 kb
****************************************************************/ //BZOJ 2982
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*=sign;
}
/*******************tamplate********************/
const int N=,P=;
int fac[N],inv[N],n,m;
int pow(int a,int b){
int r=;
for(;b;b>>=,a=a*a%P)
if (b&) r=r*a%P;
return r;
}
void calc(){
fac[]=;
F(i,,P-) fac[i]=fac[i-]*i%P;
inv[P-]=pow(fac[P-],P-); inv[]=;
D(i,P-,) inv[i]=inv[i+]*(i+)%P;
}
inline int c(int n,int m){
if (n<m) return ;
if (n<P && m<P) return fac[n]*inv[m]%P*inv[n-m]%P;
return c(n%P,m%P)*c(n/P,m/P)%P;
}
int main(){
int T=getint();
calc();
while(T--){
n=getint(); m=getint();
printf("%d\n",c(n,m));
}
return ;
}