Problem 2020 组合
Accept: 714 Submit: 1724
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)模p等于p进制数上各位的C(ni,mi)模p的乘积。利用该定理，可以将计算较大的C(n,m)转化成计算各个较小的C(ni,mi)。该方案能支持整型范围内所有数的组合数计算，甚至支持64位整数，注意中途溢出处理。该算法的时间复杂度跟n几乎不相关了，可以认为算法复杂度在常数和对数之间。
【卢卡斯（Lucas）定理】
Lucas定理用来求C（a,b）mod p的值,其中p为素数。
数学表达式为：
Lucas(a,b,q)=C(a%q,b%q)*Lucas(a/p,b/p,p);
Lucas(a,0,q)=0;
通过这个定理就可以很方便的把大数的组合转化成小数。但其中还是要求C(a%q,b%q)%p，所以这里引入逆元来求。
【定义】若整数a,b,p, 满足a·b≡1(mod p).则称a 为b 模p 的乘法逆元, 即a=b– 1mod p.其中, p 是模数。
应用到组合数中来就是:
a!/[b!*(a-b)!] % p == a! * [b!*(a-b)!]-1 %p
【逆元求法】：
对于正整数
和
，如果有
，那么把这个同余方程中
的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为
。
应用费马小定理，ap-1=1 mod p ，即 a*ap-2=1 mod p
也就是说 ap-2就是a的逆元。
当然这里求出来的逆元是在取模p的逆元，对我们最终目标没有影响。这也是比较方便而且比较好的方法。
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define sfl(n) scanf("%I64d", &n)
#define pfi(n) printf("%d\n", n)
#define pfl(n) printf("%I64d\n", n)
#define MAXN 1000005ll quickpow(ll m, ll n , ll k){
ll ans = ;
while(n){
if(n & )//如果n是奇数
ans = (ans * m) % k;
n = n >> ;//位运算“右移1类似除2”
m = (m * m) % k;
}
return ans;
}//ll quickpow(ll a, ll b, ll p)
//{
// ll ans = 1;
// a %= p;
// while(b)
// {
// if(b & 1)
// {
// ans = ans * a % p;
// b--;
// }
// b >>= 1;
// a = a * a % p;
// }
// return ans;
//}ll C(ll n, ll m, ll p)
{
if(m > n) return ;
ll ans = ;
for(int i = ; i <= m; i++)
{
ll a = (n - m + i) % p;
ll b = i % p;
ans = ans * (a * quickpow(b, p - , p) % p) % p;
}
return ans;
}ll Lucas(ll n, ll m, ll p)
{
if(m == ) return ;
else
return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
int main()
{
int T;
sfi(T);
while(T--)
{
ll n, m, p;
sfl(n), sfl(m), sfl(p);
pfl(Lucas(n, m, p));
}
return ;
}
