Problem 2020 组合
Accept: 130 Submit: 350
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！
Input
输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)
Output
对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。
Sample Input
2 5 2 3 5 2 61
Sample Output
1 10
Source
FOJ有奖月赛-2011年04月（校赛热身赛）
这个题非常裸露，直接问我们组合数去模
于是应该果断想到lucas定理。
这里注意到，对于一个质数p，i对p的逆元可以不用扩展欧几里得进行求解
可以有公式：re=i^(p-2)得到
我的代码：
#include<stdio.h>
__int64 power(__int64 a,__int64 b,__int64 n)
{
__int64 res=1;
for(;b;b>>=1,a=a*a%n)
if(b&1)
res=res*a%n;
return res;
}
__int64 cal(__int64 n,__int64 r,__int64 p)
{
__int64 i,res=1,re;
for(i=1;i<=r;i++)
{
res=res*(n-i+1)%p;
re=power(i,p-2,p);
res=res*re%p;
}
return res;
}
__int64 lucas(__int64 n,__int64 m,__int64 p)
{
if(n<m)
return 0;
else
return cal(n,m,p);
}
int main()
{
__int64 n,m,p,res;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d",&n,&m,&p);
res=1;
while(n&&m)
{
res=res*lucas(n%p,m%p,p);
if(res==0)
break;
n=n/p;
m=m/p;
}
printf("%I64d\n",res);
}
return 0;
}