组合数

\(C^{b}_{a}\)从a个物品里选择b件物品的选法

算法一

暴力枚举:

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    
    for (int i = 1, j = a; i <= b; i ++ , j -- ){
        res = res * j;
        res = res / i;
    }
    cout << res << endl;
}

算法二

应用性质: \(C^{b}_{a} = C^{b - 1}_{a - 1} + C^{b}_{a - 1}\)
预处理数组\(c[a][b](C^{b}_{a})\)
时间复杂度: \(O(n^2)\)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2010;
const int p = 1e9 + 7;

int c[N][N];

void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (j == 0)     //从i个中一个都不选
                c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;      //递推
}

int main()
{
    init();
    int n;
    cin >> n;
    
    while (n -- ){
        int a, b;
        cin >> a >> b;
        cout << c[a][b] % p << endl;
    }
    
    return 0;
}

算法三

初始化所有的\(!x\), 应用公式\(C^{b}_{a} = \frac{!a}{!(a - b)!b}\)求解
注意求解过程中涉及到除法, 不能直接进行取模操作, 需要预处理\(!x\)的同时, 预处理\(!x\)的逆元
时间复杂度: \(O(NlogN)\)

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int p = 1e9 + 7;
const int N = 1e5 + 10;

int fact[N], infact[N];

int n;

int qpow(int a, int b, int p)
{
    int res = 1;
    while (b){
        if (b & 1)
            res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

void init()
{
    fact[0] = infact[0] = 1;        //阶乘初始化为1
    for (int i = 1; i <= N ; i ++ ){
        fact[i] = (LL)fact[i - 1] * i % p;
        infact[i] = (LL)infact[i - 1] * qpow(i, p - 2, p) % p;
    }
}

int main()
{
    init();
    
    cin >> n;
    while (n -- ){
        int a, b;
        cin >> a >> b;
        cout << (LL)fact[a] * infact[b] % p * infact[a - b] % p << endl;
    }
    
    return 0;
}

算法四

Lucas定理

\(C^{b}_{a} = C^{b mod p}_{a mod p} + C^{b / p}_{a / p}\)
(证明详见yxc)
适用于:\(a\), \(b\) 范围在\(1 - 1e18\),且\(p\)的范围较小\((1e5)\)
对于每一对\(a,b\), 递归求解\(C^{b / p}_{a / p}\), 对于\(C^{b mod p}_{a mod p}\)由于数据较小, 可以直接求解, 当\(a < p 且 b < p\), 达到边界。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int p;

int qpow(int a, int b)
{
    int res = 1;
    while (b){
        if (b & 1)
            res = (LL)res * a % p;
        b >>= 1;
        a = (LL)a * a % p;
    }
    
    return res;
}

int C(int a, int b)
{

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- ){
        res = (LL)res * j % p;
        res = (LL)res * qpow(i, p - 2) % p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p)
        return C(a, b);
    else
        return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p; 
}

int main()
{
    int n;
    cin >> n;
    
    while (n -- ){
        LL a, b;
        cin >> a >> b >> p;
        
        cout << lucas(a, b) << endl;
    }
    
    return 0;
    
}

组合数

原文：https://www.cnblogs.com/lhqwd/p/14634603.html