组合数学

抽屉原理

• 将n+1个物体划分为n组，至少有一组有两个及以上的物体

• 将n个物体划分为k组，至少存在一个分组，含有大于等于个物体

插板法

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

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

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

容斥原理

前置知识：德摩根律

简单形式：设A,B是分别具有性质和的元素集合，则

推广：设集合S的子集具有性质，…，具有性质，则

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

2. 集合S不具有性质之一的元素个数为$ _{i=1}^{n} ||=|S|-(|A_i|-|A_iA_j|+|A_iA_jA_k|-+(-1)^n|_{i=1}{n}A_i| )$

求组合数

求解(其中p为质数)

阶乘+乘法逆元

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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()进行初始化！！！

卢卡斯定理

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

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

1
2
3
4

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

多重全排列

由个1，个2，，个t组成的排列（其中），它的全排列为