Lucas定理
求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）
学习这个定理之前，我们需要明确几个概念：
组合数公式：
c(n,m)=n!/m!(n-m)! (从n个不同元素中取出m个元素的组合数)
同余：
已知数a，b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m，记为a≡b(mod m)
费马小定理：
a^(p-1)≡1 (mod p) 等价于 a*a^(p-2)≡1 (mod p)
乘法逆元：
定义：
满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。（实际上可以看做a*k=1） 为什么要有乘法逆元呢？
当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。 证：（其实很简单。。。）
根据b*k≡1 (mod p)有b*k=p*x+1。
k=(p*x+1)/b。
把k代入(a*k) mod p，得：
(a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//p*[(a*x)/b] mod p=0
所以原式等于：(a/b) mod p 好啦，当你把这些概念都吃透时，你会发现太阳已经落山了（O(∩_∩)O~/手动滑稽），现在我们可以考虑Lucas定理了，实际上它的原理就是：
求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）
n=n[k]*p^k+n[k-1]*p^(k-1)+…+n[1]*p+n[0]
m=m[k]*p^k+m[k-1]*p^(k-1)+…+m[1]*p+m[0]
把n和m都变成p进制数
c(n,m)就等于每个c(n[i],m[i])(mod p) 都乘起来，在这里i=0~k 这里写代码片 #include #include #include #include #include #define LL long long using namespace std; LL n,m,mod; LL KSM(LL a,LL p) //a^p,快速幂 { a%=mod; LL tmp=1; while (p) { a=(a*a)%mod; if (p&1) tmp=(tmp*a)%mod; p>>=1; } return tmp; } LL cf(LL FM,LL mod) //求逆元 { return KSM(FM,mod-2); //费马小定理a*a^(p-2)≡1 (mod p),a和a^(p-2)互为逆元 } LL C(int m,int n) //c(m,n)=m!/n!(m-n)! { if (n>m) return 0; int i; LL FZ=1,FM=1; for (i=m-n+1;i<=m;i++) FZ=i*FZ%mod; //组合公式，FZ是分子，FM当然是分母啦 for (i=1;i<=n;i++) FM=FM*i%mod; return (FZ*cf(FM,mod))%mod; //=>(FZ/FM)%mod } LL Lucas(int m,int n) //从m个中选n个 { if (n>m) return 0; LL ans=1; while (n) { ans=ans*C(m%mod,n%mod)%mod; n/=mod; m/=mod; } return ans; } int main() { scanf("%lld%lld%lld",&n,&m,&mod); printf("%lld",Lucas(n,m)); return 0; }