Problem 2020 组合
Accept: 981 Submit: 2384
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定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n,m,p)= c(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;
而
c(a,b)=a! * (b!*(a-b)!)^(p-2) mod p
也= (a!/(a-b)!) * (b!)^(p-2)) mod p
这里，其实就是直接求 (a!/(a-b)!) / (b!) mod p
由于 (a/b) mod p = a * b^(p-2) mod p (费马小定理而来)
http://acm.fzu.edu.cn/problem.php?pid=2020
求C(n,m) mod p的结果
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 int cas; 5 LL n,m,p; 6 LL ksm(LL x,LL y){ 7 LL an(1); 8 while (y){ 9 if (y&1) 10 an=an*x%p; 11 x=x*x%p; 12 y>>=1; 13 } 14 return an; 15 } 16 LL c(LL x,LL y){ 17 int i,j; 18 LL an(1); 19 if (x<y) 20 return 0; 21 for (i=1;i<=y;i++) 22 an=an*(x-i+1)%p*ksm(i,p-2)%p; 23 return an; 24 } 25 LL lucas(LL x,LL y){ 26 LL an(1); 27 while (x&&y){ 28 an=an*c(x%p,y%p); 29 if (an==0) 30 return 0; 31 an%=p; 32 x/=p,y/=p; 33 } 34 return an; 35 } 36 int main(){ 37 freopen ("lucas.in","r",stdin); 38 freopen ("lucas.out","w",stdout); 39 int i,j; 40 scanf("%d",&cas); 41 while (cas--){ 42 scanf("%lld%lld%lld",&n,&m,&p); 43 printf("%lld ",lucas(n,m)); 44 } 45 return 0; 46 }