排列组合

排列组合是组合数学中最基础的部分，这里只介绍方案和计数如何做。

方案

输出所有的排列/组合方案，需要利用深度优先搜索做。

排列方案

从 ${1∼n}$ 这 ${n}$ 个整数中随机选出 ${m}$ 个， 有${A_{n}^{m}}$种排列，请输出所有的排列方案。

dfs

#include <vector>
#include <iostream>

using namespace std;
const int N = 10;

int n, m;
// vector<int> bit;

vector<int> choosen;
bool visited[N] = {0}; // 需要一个visited数组

void dfs(int depth, int select) {
    // 剪枝
    if (select > m || n + 1 - depth < m - select) {
        return;
    }
    
    // 递归边界
    if (select == m) {
        for (int i = 0; i < choosen.size(); i ++) {
            printf("%d ", choosen[i]);
        }
        cout << endl;     
        return;
    }
    if (depth == n + 1) return;
    
    for (int i = 1; i <= n; i ++) {
        if (!visited[i]) {
            visited[i] = true;
            choosen.emplace_back(i); // emplace_back(bit[i]);
            dfs(depth + 1, select + 1);
            // 回溯
            choosen.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

练习eg:

LeetCode-46. 全排列

组合方案

从 ${1∼n}$ 这 ${n}$ 个整数中随机选出 ${m}$ 个， 有${C_{n}^{m}}$种组合，请输出所有的组合方案。

dfs

#include <vector>
#include <iostream>

using namespace std;

int n, m;
// vector<int> bit;
vector<int> choosen;

void dfs(int depth, int select) {
    // 剪枝
    if (select > m || n + 1 - depth < m - select) {
        return;
    }
    
    // 递归边界
    if (select == m) {  
        for (int i = 0; i < choosen.size(); i ++) {
           	printf("%d ", choosen[i]);
        }
        cout << endl;
        return;
    }
    if (depth == n + 1) return;
        
    choosen.emplace_back(depth); // emplace_back(bit[depth]);
    dfs(depth + 1, select + 1);
    // 回溯
    choosen.pop_back();
    dfs(depth + 1, select);
}

int main() {
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

练习eg:

LeerCode-77. 组合

LeetCode-78. 子集

---

计数

只需要算方案数量时，可以使用数学公式推导。

排列计数

从 ${1∼n}$ 这 ${n}$ 个整数中随机选出 ${m}$ 个， 有${A_{n}^{m}}$种排列，由于结果可能很大，请将结果对$1e9 + 7$取模返回。

排列计数很简单，可以利用下列公式直接计算：

$A^m_n = n(n - 1)(n - 2)\ldots (n - m + 1)$

const int MOD = 1e9 + 7;

using int64 = long long;

int arra(int n, int m) {
    int res = 1;
    for (int i = n - m + 1, i <= m; i++) {
        res = (int64)res * i % MOD;
    }
    return res;
}

组合计数

从 ${1∼n}$ 这 ${n}$ 个整数中随机选出 ${m}$ 个， 有${C_{n}^{m}}$种组合，由于结果可能很大，请将结果对$1e9 + 7$取模返回。

根据$n$、$m$范围和询问次数的不同，可以选择以下三种解法：

---

O(n ^ 2)预处理，1次询问O(1)

利用下列递推式，可以把该问题看作一个线性DP：

$C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1}$

$C_{n}^{0} = C_{n-1}^{0} = \ldots = C_{1}^{0} = C_{0}^{0} = 1$

#include <vector>
#include <iostream>

using namespace std;

using int64 = long long;

const int N = 2000 + 7;
const int MOD = 1e9 + 7;

vector<vector<int64>> c(N + 1, vector<int64>(N + 1));
void comb(int m, int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        }
    }
}

int main() {
    comb(2000, 2000);
    int n;
    cin >> n;
    int a, b;
    while (n--) {
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
}

• 时间复杂度：$O(n^2)$预处理
• 空间复杂度：$O(n^2)$

---

O(n)预处理，1次询问O(n）

这种就比较适合只询问1次的。

利用递推式：

$C_{n}^{m} = \frac{n - m + 1}{m}C_{n}^{m - 1}$

这个递推式中出现了除法，由于结果要对$1e9 + 7$取模，因此要对系数$\frac{n - m + 1}{m}$的分母$m$求乘法逆元$m^{-1}(mod \ p)$

#include <vector>
#include <iostream>

using namespace std;

using int64 = long long;

const int N = 1e5;
const int MOD = 1e9 + 7;

vector<int64> inv(N + 1);

void init() {
    // 线性求逆元
    inv[1] = 1;
    for (int i = 2; i <= N; i++) {
		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
}

int comb(int n, int m) {
    int res = 1; // 初值C(n, 0) = 1
    for (int i = 1; i <= m; i++) {
        res = (int64)res * (n - i + 1) % MOD * inv[i] % MOD;
    }
    return res;
}

int main() {
    init();
    
    int a, b;
    cin >> a >> b;
    cout << comb(a, b) << endl;
}

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

---

O(nlogn)预处理，1次询问O(1)

直接利用公式：

$C^m_n = \frac{n !} {(n - m)! * m!}$

关键就是要求分母 $(n - m)!$和$m$!的逆元$(n - m)!^{-1}(mod \ p)$和$m! ^{-1}(mod \ p)$

我们可以在计算阶乘的过程中，把阶乘和阶乘的逆元分别保存在两个数组fact[N]和infact[N]中

#include <vector>
#include <iostream>

using namespace std;

using int64 = long long;

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

int fact[N], infact[N];

int fast_pow(int x, int n) {
    int res = 1;
    for (; n; n = n >> 1) {
        if (n & 1) {
            res = (int64)res * x % MOD;
        }
        x = (int64)x * x % MOD;
    }
    return res;
} 

int main() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (int64)fact[i - 1] * i % MOD;
        infact[i] = (int64)infact[i - 1] * fast_pow(i, MOD - 2) % MOD;
    }
    
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        printf("%d\n", (int64)fact[a] * infact[a - b] % MOD * infact[b] % MOD);
    }
    
    return 0;
}