组合数学

抽屉原理

将n+1个物体划分为n组，至少有一组有两个及以上的物体
将n个物体划分为k组，至少存在一个分组，含有大于等于$\lceil \frac{n}{k}\rceil$个物体

插板法

n个完全相同的元素分为k组，每组至少一个元素，一共有多少分发

我们通过插板子来实现分组，用k-1块板子插入n-1个空中，即有$ $中分发

若每组允许为空，我们将条件转化为在n+k个元素形成的n+k-1个空里面插板子，即有$ $

容斥原理

前置知识：德摩根律

简单形式：设A,B是分别具有性质$P_1$和$P_2$的元素集合，则$|A\cup B|=|A|+|B|-|A\cap B|$

推广：设集合S的子集$A_1$具有性质$P_1$，…，$A_n$具有性质$P_n$，则

集合S至少具有性质$P_1,P_2,\cdots,P_n$之一的元素个数为$ _{i=1}^{n} |A_i|=|A_i|-|A_iA_j|+|A_iA_jA_k|-+(-1)^n|_{i=1}{n}A_i| $
集合S不具有性质$P_1,P_2,\cdots,P_n$之一的元素个数为$ _{i=1}^{n} ||=|S|-(|A_i|-|A_iA_j|+|A_iA_jA_k|-+(-1)^n|_{i=1}{n}A_i| )$

求组合数

求解$\binom{n}{m}\mod{p}$(其中p为质数)

阶乘+乘法逆元

求出阶乘n!,m!,(n-m)!，每次乘法后取模
求出阶乘对应的乘法逆元

这里我们可以预处理掉对应阶乘与对应逆元，在计算组合数时直接计算

ll fac[N], infac[N];

// 快速幂计算
ll qpow(ll a, ll n, ll m) {
    ll r = 1;
    while (n) {
        if (n & 1) r = r * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return r;
}

// 初始化阶乘和逆元
void init_fac() {
    fac[0] = infac[0] = 1;
    for (ll i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        infac[i] = qpow(fac[i], mod - 2, mod); // 使用快速幂计算逆元
    }
}

// 组合数计算
ll C(ll n, ll m) {
    if (m > n || m < 0) return 0; // 边界条件
    return fac[n] * infac[m] % mod * infac[n - m] % mod;
}

别忘了调用init_fac()进行初始化！！！

卢卡斯定理

\[ \begin{array}{c}C_{a}^{b}\equiv C_{\lfloor\frac{a}{p}\rfloor}^{\lfloor\frac{b}{p}\rfloor} \cdot C_{a \bmod p }^{b\bmod p}\pmod{p}\end{array} \]

其中前半部分可以用卢卡斯定理递归求解，后半部分用上方方法求解

卢卡斯定理可以优化求解速度，而且适用于求解a，b较大而p较小的情况

ll lucas(ll n, ll m){
  if (!m)return 1;
  return lucas(n/mod, m/mod)*C(n%mod,m%mod)%mod;
}

多重全排列

由$r_1$个1，$r_2$个2，$\cdots$，$r_t$个t组成的排列（其中$r_1+r_2+\cdots +r_t=n$），它的全排列为 \[ \frac{n!}{r_1!r_2!\cdots r_t!} \]

红魔咖啡馆

【数学】组合数学