组合数取模问题为求 $C_{n}^m % p$ 的值. 根据 $n$,$m$,$p$ 取值不同, 方法不同.
在此之前我们先看些前置技能:
同余定理:$ab(mod\ m)$
性质:
1. 传递性: 若 $ab(mod\ m)$,$bc(mod\ m)$, 则 $ac(mod\ m)$;
2. 同余式相加: 若 $ab(mod\ m)$,$cd(mod\ m)$, 则 $a±cb±d(mod\ m)$;
3. 同余式相乘: 若 $ab(mod\ m)$,$cd(mod\ m)$, 则 $acbd(mod\ m)$.
逆元 (数论倒数): 对于正整数 $a$ 和 $m$, 如果有 $ax1(mod\ m)$, 那么把这个同余方程中 $x$ 的最小正整数解称为 $a mod\ m$ 的逆元.
为什么叫数论倒数呢, 因为没有 $mod$ 操作, 那么 $x$ 就相当于 $a$ 的倒数, 有 $mod$ 操作时效果上和倒数一样. 同时我们把 $a$ 的逆元写做:$inv(a)$.
逆元求解一般用扩展欧几里得算法, 如果 $m$ 为素数, 那么还可以根据费马小定理得到逆元为 $a^{m-2} mod\ m$.
扩展欧几里得算法和费马小定理求解逆元具有局限性, 两种算法都要求 a 和 m 互素.
1. 扩展欧几里得:$a*x + b*y = 1$
解 $x$ 就是 $a$ 关于 $b$ 的逆元, 解 $y$ 就是 $b$ 关于 $a$ 的逆元
$a*x \% b + b*y \% b = 1 \% b$
- $a*x \% b = 1 \% b$
- $a*x = 1 (mod\ b)$
2. 费马小定理:$a\hat{}(p-1)1 (mod\ p)$
两边同时除以 $a$,$a\hat{}(p-2)inv(a)(mod\ p)$; 即 $inv(a)a^(p-2)(mod\ p)$
Lucas 定理:
- $n=n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0$
- $m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0$
得到:$C_n^m=\prod\limits_{i=0}^{k}C_{ni}^{mi}(mod\ p)$
具体代码中实现:$Lucas(n,m,p)=C(n\%p,m\%p)*Lucas(n/p,m/p,p)\%p $
经典例题 1: http://acm.fzu.edu.cn/problem.php?pid=2020
$1 <= m <= n <= 10^9, m <= 10^4, m <p < 10^9, p 是素数 $,$m$ 比较小,$n$,$p$ 比较大的情况.
该题 cin 输入会比较快, 怀疑是 scanf 读入 %lld 比较耗时, 或者是 OJ 问题.
解决方案 1:Lucas 定理
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- LL fast_power(LL a,LL b,LL p){
- LL ans=1;
- a%=p;
- while(b){
- if(b&1) ans=(ans*a)%p;
- a=(a*a)%p;
- b>>=1;
- }
- return ans;
- }
- LL C(LL a,LL b,LL p){
- if(b>a) return 0;
- if(a==b) return 1;
- LL ans1=1,ans2=1;
- for(LL i=1;i<=b;i++){
- ans1=ans1*(a-i+1)%p;
- ans2=ans2*i%p;
- }
- return ans1*fast_power(ans2,p-2,p)%p;
- }
- LL Lucas(LL a,LL b,LL p){
- if(b==0) return 1;
- return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- LL n,m,p;
- cin>>n>>m>>p;
- cout<<Lucas(n,m,p)<<endl;
- }
- return 0;
- }
- View Code
解决方案 2: 暴力 + 逆元
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- LL fast_power(LL x,LL n,LL mod){
- LL ans=1;
- x%=mod;
- while(n){
- if(n&1) ans=(ans*x)%mod;
- n>>=1;
- x=(x*x)%mod;
- }
- return ans;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- LL n,m,p;
- cin>>n>>m>>p;
- LL ans1=n,ans2=1;
- for(LL i=1;i<m;i++){
- ans1=ans1*(n-i)%p;
- ans2=ans2*i%p;
- }
- ans2=ans2*m%p;
- cout<<ans1*fast_power(ans2,p-2,p)%p<<endl;
- }
- return 0;
- }
- View Code
经典例题 2: http://codeforces.com/gym/101775/problem/A
$1??N??10^9,3??K??10^5,mod=1000000007$
组合数取模
来源: http://www.bubuko.com/infodetail-2616256.html