1）根据一下公式，直接计算
C(n,m) mod p = n*``*(n-m+1)/(1*``*m) mod p
计算分别分子nn、分母mm中p的个数和对p的余数，若分子中p的个数多余分母中p的个数，则结果为0，
若不是，则原式变为nn/mm mod p (nn,p)=1,(mm,p)=1
此时如何求逆元变得至关重要，以下有两种解法。
2） Lucas 定理：是用来求 C(n,m) mod p的值,p是素数。
描述为:
Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(n,0,p)=1;
而
C(a,b)=a*(a-1)*```*(a-b+1)/(1*2*```*b)%p,
其中分子为aa分母为bb，故C(a,b)=aa/bb%p,（此时求法同上）
至此逆元的求法也很重要，逆元的求法，如下会有所解释。
补充知识：逆元的求法
(a/b) mod p=a*(b逆) mod p
b*x=1(mod p) x就是b的逆元
而b逆可以利用扩展欧几里德或欧拉函数求得：
1).扩展欧几里德：b*x+p*y=1 有解，x就是所求
2).欧拉函数：b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2)
综上所述，其实方法一可以看成是暴力计算，而方法二中只是将大数变为数，再采用方法一的方法计算，这样时间上会有所降低。
方法一：直接计算，代码如下：
#include<stdio.h>
#define LL long long
int pnum, x, y;
int getMultMod(int start, int end, int p) {
int i, j;
LL res;
for (i = start, res = 1, pnum = 0; i <= end; i++) {
if (i % p == 0) {
j = i;
while (j % p == 0) {
pnum++;
j /= p;
}
res = res * j % p;
} else {
res = res * i % p;
}
}
return (int) (res % p);
}
void extend_gcd(int a, int b) {
int xx;
if (b == 0) {
x = 1, y = 0;
return;
}
extend_gcd(b, a % b);
xx = x;
x = y, y = xx - a / b * y;
}
void solve(int n, int m, int p) {
int a, b, apnum, bpnum;
LL res;
a = getMultMod(n - m + 1, n, p);
apnum = pnum;
b = getMultMod(1, m, p);
bpnum = pnum;
if (apnum > bpnum) {
puts("0");
return;
} else {
extend_gcd(b, p);
res = (LL) x;
res = (res % p + p) % p;
res = res * a % p;
printf("%I64d\n", res);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, n, m, p;
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &n, &m, &p);
solve(n, m, p);
}
return 0;
}
根据求逆元的不同也可以对其中的若干方法进行改写如下所示：
int modular_exp(int a, int b, int p) {
LL res, temp;
res = 1 % p, temp = a % p;
while (b) {
if (b & 1) {
res = res * temp % p;
}
temp = temp * temp % p;
b >>= 1;
}
return (int) res;
}
void solve(int n, int m, int p) {
int a, b, apnum, bpnum;
LL res;
a = getMultMod(n - m + 1, n, p);
apnum = pnum;
b = getMultMod(1, m, p);
bpnum = pnum;
if (apnum > bpnum) {
puts("0");
return;
} else {
res = modular_exp(b, p - 2, p);
res = res * a % p;
printf("%I64d\n", res);
}
}
方法二：利用Lucas 定理，代码如下所示：
#include<stdio.h>
#define LL long long
int x, y;
void extend_gcd(int a, int b) {
int xx;
if (b == 0) {
x = 1, y = 0;
return;
}
extend_gcd(b, a % b);
xx = x;
x = y, y = xx - a / b * y;
}
int C(int a, int b, int p) {
int i;
LL resa, resb, res;
if (b > a) {
return 0;
}
for (i = 0, resa = 1, resb = 1; i < b; i++) {
resa = resa * (a - i) % p, resb = resb * (b - i) % p;
}
extend_gcd(resb, p);
res = (LL) x;
res = (res % p + p) % p;
res = res * resa % p;
return (int) res;
}
void solve(int n, int m, int p) {
int a, b;
LL res;
res = 1;
while (n || m) {
a = n % p, b = m % p;
res = res * C(a, b, p) % p;
n /= p, m /= p;
}
printf("%I64d\n", res);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, n, m, p;
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &n, &m, &p);
solve(n, m, p);
}
return 0;
}
根据求逆元的不同，以上若干方法又可以改写为：
int modular_exp(int a, int b, int p) {
LL res, temp;
res = 1 % p, temp = a % p;
while (b) {
if (b & 1) {
res = res * temp % p;
}
temp = temp * temp % p;
b >>= 1;
}
return (int) res;
}
int C(int a, int b, int p) {
int i;
LL resa, resb, res;
if (b > a) {
return 0;
}
for (i = 0, resa = 1, resb = 1; i < b; i++) {
resa = resa * (a - i) % p, resb = resb * (b - i) % p;
}
res = modular_exp(resb, p - 2, p);
res = res * resa % p;
return (int) res;
}
总结：此类问题，涉及到的方法有，求逆元的方法（扩展欧几里德算法，欧拉函数的知识（有涉及到大数取余）），Lucas定理，小组合数取余。