网上证明很多，虽然没看懂。。。。
主要解决大组合数取模的情况
费马小定理求大组合数：
a^(p-1)=1%p;
两边同除a
a^(p-2)=1/a%p;
C（n,m）= n!/(m!*(n-m)!)
所以C（n,m）=f(n)*qpow(f(m)*f(n-m),MOD-2))%MOD
预处理组合数f
百度之星2016 1003
先推公式，再lucas
p很大的情况 1e9+7
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define clc(a,b) memset(a,b,sizeof(a))
#include <bits/stdc++.h>
const int maxn = ;
const int inf=0x3f3f3f3f;
const double pi=acos(-);
typedef long long LL;
using namespace std;
const LL MOD = 1e9+; LL exp_mod(LL a, LL b, LL p)
{
LL res = ;
while(b != )
{
if(b&) res = (res * a) % p;
a = (a*a) % p;
b >>= ;
}
return res;
} LL Comb(LL a, LL b, LL p)
{
if(a < b) return ;
if(a == b) return ;
if(b > a - b) b = a - b; LL ans = , ca = , cb = ;
for(LL i = ; i < b; ++i)
{
ca = (ca * (a - i))%p;
cb = (cb * (b - i))%p;
}
ans = (ca*exp_mod(cb, p - , p)) % p;
return ans;
} LL Lucas(int n, int m, int p)
{
LL ans = ; while(n&&m&&ans)
{
ans = (ans*Comb(n%p, m%p, p)) % p;
n /= p;
m /= p;
}
return ans;
} int main()
{
int n, m;
LL p;
while(~scanf("%d%d", &n, &m))
{
p=MOD;
printf("%I64d\n", Lucas(n+m-, m-, p));
}
return ;
}
p在100000左右
HDU 3037
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define clc(a,b) memset(a,b,sizeof(a))
#include <bits/stdc++.h>
const int maxn = ;
const int inf=0x3f3f3f3f;
const double pi=acos(-);
typedef long long LL;
using namespace std;
//const LL MOD = 1e9+7; LL PowMod(LL a,LL b,LL MOD){
LL ret=;
while(b){
if(b&) ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=;
}
return ret;
}
LL fac[];
LL Get_Fact(LL p){
fac[]=;
for(int i=;i<=p;i++)
fac[i]=(fac[i-]*i)%p;
}
LL Lucas(LL n,LL m,LL p){
LL ret=;
while(n&&m){
LL a=n%p,b=m%p;
if(a<b) return ;
ret=(ret*fac[a]*PowMod(fac[b]*fac[a-b]%p,p-,p))%p;
n/=p;
m/=p;
}
return ret;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
LL n,m,p;
scanf("%I64d%I64d%I64d",&n,&m,&p);
Get_Fact(p);
printf("%I64d\n",Lucas(n+m,m,p));
}
return ;
}