數論-組合數的求法探究

組合數的簡述

• 組合數一般表示為 C n m C_n^m Cnm​，也表示為

  ( m n ) \left( \begin{matrix}m \\n\\\end{matrix}\right) (mn​)。

• 在數論中，一般需要求的是組合數取模，即 C n m   %   p C_n^m \ \% \ p Cnm​ % p,其中大多數時候p=1e9+7

• 組合數的計算公式為

  C n m = n ! m ! ( n − m ) ! C_n^m=\dfrac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​

• 由于要求取模，這時直接得出的結果往往過于巨大（這也是取模的原因），是以不可以算出結果再取模。此外，沒有模除法性質（即(a/b)%p=((a%p)/(b%p)%p不成立），是以要用到逆元

楊輝三角法

我們先考慮一種不用逆元的方法：楊輝三角法

原理分析

楊輝三角具有如下性質：

1. 楊輝三角上的每一個數字都等于它的左上方和右上方的和（除了邊界）
2. 第n行，第m個就是，就是C(n, m) （從0開始）

實作代碼（複雜度O(N^2)）

#include<cstdio>
const int N = 2000 + 5;
const int MOD = (int)1e9 + 7;
int comb[N][N];//comb[n][m]就是C(n,m)
void init(){
    for(int i = 0; i < N; i ++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= MOD;
        }
    }
}
int main(){
    init();
}
           

逆元法

原理分析

1. 什麼是逆元：
   • 定義：對于a和p（a和p互素），若a * b % p ≡ 1，則稱b為a % p的逆元，記作 b = inv(a) mod p 或 b = inv(a, p)
   • 性質：(a / b) % p ⇔ \Leftrightarrow ⇔ (a * inv(b)) % p = (a % p + inv(b) % p) % p
2. 如何求逆元：
   • 費馬小定理：對于a和素數p，滿足a ^ ( p - 1) ≡ 1 (mod p)
   • 上式等價于 a ^ （p - 2) * a ≡ 1 (mod p)，是以inv(a) = a ^ (p-2)
   • 逆元還有其他的求法，此處不一一列出。

3. 利用逆元求組合數取模

   預先疊代求出所有階乘，然後求出對應的逆元，最後利用逆元乘法取模性質即可

實作代碼（複雜度O(N)）

#include<cstdio>
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int F[N], Finv[N], inv[N];//F是階乘，Finv是逆元的階乘 
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){//comb(n, m)就是C(n, m) 
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}
int main(){
    init();
}
           

盧卡斯法

原理分析

1. 适用情景： n<=1e18,m<=1e18,p<=1e5 ， 即n、m很大但p很小
2. 盧卡斯定理：C(n, m) % p = C(n / p, m / p) * C(n % p, m % p) % p
3. 實作思路：遞歸求取即可

實作代碼

LL Lucas(LL n, LL m, int p){
        return m ? Lucas(n/p, m/p, p) * comb(n%p, m%p, p) % p : 1;
}
           

參考部落格

1. https://www.cnblogs.com/linyujun/p/5194189.html
2. https://blog.csdn.net/ajaxlt/article/details/86544074