排列组合

前置知识

小学数学

目标

普及组初赛阶段，排列组合方面，最少必要知识

排列数

组合数

组合数公式

组合数代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;

ll C(int n, int m){
    ll sum = 1ll;
    for (int i = 1; i <= m; i++)
        sum = sum * (n - m + i) / i;

    return sum;
}

int main(){
    cin >> n >> m;
    cout << C(n, m) << '\n';

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 110;

int n, m;
ll C[N][N];

int main(){
    cin >> n >> m;

    C[0][0] = 1;
    for (int i = 1; i <= n; i++){
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j <= n; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }

    cout << C[n][m] << '\n';

    return 0;
}

常见计数方法

特殊优先

捆绑与插空

插板法原理及应用

抽屉原理

又称，鸽巢原理。将 n + 1 个物体，划分成 n 组，那么有至少一组有两个（或以上）的物体。用反证法证明。

错位排列

容斥原理

Catalan数

说明： 一棵二叉树，根结点占 1 个结点，假设左子树 x 个结点，那么右子树有 n - 1 - x 个结点。 枚举 x for 0 ... n-1，即可得到上面的式子。

杨辉三角

总结

排列数，组合数，计算公式，公式变形，计算组合数的代码 特殊优先，捆绑插空，插板法 抽屉原理，错位排列，要会证明 容斥原理，会经典计算 Catanlan数，常见公式背下来 杨辉三角

参考

排列组合 - OI Wiki 插板法原理及应用_公考楚香凝_新浪博客 彻底搞懂错排公式_错排个数_bengshakalakaka的博客-CSDN博客 容斥原理 - OI Wiki 卡特兰数（Catalan）公式、证明、代码、典例. 杨辉三角（非常厉害的网站）