comb problem black trees PC

简单记录一些错过的 / Educational 的组合数学问题 / 计数问题。

一些基本模型

小球模型

Reference: lleozhang 的博客

有区别好比做排列，没区别好比做组合。

默认 \(n\) 个小球，\(m\) 个盒子。

或者说，小球有区别可以理解成有 \(n\) 个不同元素，一般需要考虑 对于每个小球都决策（一般是递推）。

盒子有区别则可以理解为，对于某个方程求有多少组解 \(\{x_i\}\)，如果小球没有区别，\(x_i\) 就是一个数字，如果小球有区别，那么\(x_i\) 就是一个集合。

允不允许有空盒子就等价于 \(x_i\) 的限制。

所以小球模型都可以抽象成 广义的线性不定方程的解的组数。

小球有区别，盒子有区别，允许有空盒子

直接考虑盒子不太好考虑，直接考虑球，

每个小球有 \(m\) 种放法，乘法原理有 \(m^n\) 种可能。

小球有区别，盒子有区别，不允许有空盒子

考虑设函数 \(f(n, m)\) 表示 \(n\) 个小球放到 \(m\) 个盒子里的方案数。

可以考虑当前小球放在哪里可以得到递推式： \(f(n,m) = m(f(n - 1, m) + f(n - 1, m - 1))\)。

就是考虑这个小球是放到原来有了的还是放到一个还没有球盒子里面。

因为盒子不同所以要乘 \(m\)。

边界：\(n = m, f(n, m) = n!; m > n, f(n, m) = 0\)。

小球有区别，盒子没区别，不允许有空盒子

和 「小球有区别，盒子有区别，不允许有空盒子」 类似。

还是设 \(f(n, m)\) 表示 \(n\) 小球放到 \(m\) 个盒子里的方案数。

类比上面可以得到递推式： \(f(n, m) = mf(n - 1, m) + f(n - 1, m - 1)\)。

唯一的区别是盒子不同。

这个是第二类斯特林数 \(\begin{Bmatrix}n \\ m\end{Bmatrix}\)。

快速求不会。

小球有区别，盒子没区别，允许有空盒子

简单问题，用第二类斯特林数转化一下，考虑分别放到 \(k\) 个盒子就行了。

\[ \sum\limits_{k = 1}^{m} \begin{Bmatrix}n \\ k\end{Bmatrix} \]

小球没区别，盒子有区别，不允许有空盒子

就是插板法的基础，答案 \(\dbinom{n - 1}{m - 1}\)。

小球没区别，盒子有区别，允许有空盒子

插板法公式，答案 \(\dbinom{n + m - 1}{n}\)。

小球没区别，盒子没区别，允许有空盒子

这个是分拆数，还不会

小球没区别，盒子没区别，不允许有空盒子

分拆数的变种。

一些有意思的题

一个四色定理的方案数计数

_________________
|     |__E_|     |
|  A  |__D_|  B  |
|     |  C |     |
-----------------

给这个地图上色，问方案数。

先考虑确定 A 区域和 B 区域的颜色是否相同。

因为 A，B 区域的颜色决策会导致 E,C 的颜色决策数改变。

1. 如果 A, B 同色，那么 D 就有 3 种方案，然后 E, C 就各有 2 种方案，答案 \(4\times 1 \times 3 \times 2 \times 2 = 48\)。
2. 如果 A, B 不同色，那么 D 只有 2 种方案，E, C 各自只有一种，答案 \(4 \times 3 \times 2 \times 1 \times 1 = 24\)。

最终答案 \(48 + 24 = 72\)。

这里能抽象出来的一个小 Trick：

所以对于这种 方案数问题，在某一个决策会影响之后的决策数量的时候就要分类讨论。

一个插板法的应用

扔 \(7\) 个质地均匀的骰子，出现和为 \(10\) 的概率 为 \(\dfrac{n}{6^7}\)，\(n\) 应该等于多少？

可以转化为插板法，答案是 \(\dbinom{10 - 1}{7 - 1}\)，因为变量都是 \(\le 6\) 的，多了不够了，所以直接这么做没有问题。

另外一个插板法的应用

定义 \(D(n)\) 表示将正整数 \(n\) 分解为如下形式的方案数：\(n = f_1 \times f_2 \times f_i \dots\)，其中 \(i \ge 1, f_i \ge 1\)，\((f_i, f_{j}); (f_j, f_i)\) 是不同的方案。

求 \(D(96)\)。

首先发现 \(96 = 2^5 \times 3\)，把 \(3\) 拿出来先不管，

然后 \(2^5\) 显然可以分成 \(2^{c_1}, 2^{c_2},\dots 2^{c_m}, m \le 5, c_i \ge 0\)

然后对于 \(m = i\) 的情况，可以把 \(3\) 放到这些数里面插板（可以是头尾），或者直接乘到这些数上面，所以此时的方案数是 \((i + 1 + i) \times i!\)，因为还可以全排列。

然后就只能对于每个情况硬算了。。。。。

线性求逆元

乘法逆元的定义大概就是，如果 \(a \times inv \equiv 1 (\mod p)\)，那么 \(inv\) 就是 \(a\) 在模 \(p\) 意义下的乘法逆元，一般记作 \(a^{-1}\) 或者 \(inv(a)\)。

正常来说应该用群论来解释逆元的定义，但是我懒，不想写了。

你可以理解成 \(a\times a^{-1} \equiv a\times inv \equiv1 (\mod p)\)，也就是说可以用来处理带取模的除法。

因为加减乘在取模意义下都是封闭的，但是除法就没法处理。

所以为了让除法在取模意义下也是封闭的，我们把除法转化成乘上分母的乘法逆元即可。

也就是说 \(\dfrac{a}{b} \equiv a\times b^{-1} \equiv a\times inv(b) (\mod p)\)。

有一个小注意点是，\(inv(a)\times inv(b) = inv(ab)\)，这个从定义上的封闭性即可知道。

求法可以直接用费马小定理：

如果 \(a,p\) 互质，则 \(a\) 在模 \(p\) 意义下的逆元是 \(a^{p-2}\)，快速幂即可 \(O(\log n)\) 求，这里也说明了只有 \(p\) 是质数的时候，对于任意给定的值域小于 \(2p\) 的序列都可以求出逆元。

然后我们对于一个值域为 \([1,n]\) 的数列，我们要求出每一项在 \(\mod p\) 意义下的逆元（\(p\) 是质数），这样做肯定不好搞，所以考虑一个可以线性递推的做法

首先令 \(r = i\mod p\)，令 \(\lfloor p/i\rfloor = k\)，即 \(ki+r \equiv 0(\mod p)\)。

然后就是移项，把 \(i\) 单独留一边，另外一边是一个小于 \(i\) 的数的逆元的形式。

\[ \begin{aligned} ki+r &\equiv 0 &(\mod p)\\ i &\equiv \dfrac{-r}{k} &(\mod p)\\ i &\equiv -r \times inv(k) &(\mod p)\\ i &\equiv -inv(k)\times r &(\mod p)\\ inv(i) &\equiv -k\times inv(r) &(\mod p)\\ inv(i) &\equiv -\lfloor p/i\rfloor \times inv(p \mod i) &(\mod p) \end{aligned} \]

最后一步这里有负数，加一下（如果 \(x < 0\)，则 \(x \equiv p - x (\mod p)\) ）：

\[ inv(i)\equiv (p - p/i) \times inv(p \mod i) (\mod p) \]

于是就能线性递推了，组合数啥的也能求：

const int mod = 998244353;

int inv[si], fact[si], invf[si];
void init(int n) {
    inv[1] = 1, fact[0] = invf[0] = 1;
    for(int i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 1; i <= n; ++i)
        fact[i] = 1ll * fact[i - 1] * i % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
}
int C(int n, int m) {
    if(m < 0 || n < m) return 0;
    return 1ll * fact[n] * invf[n - m] % mod * invf[m] % mod;
}
int Catalan(int n) {
    return 1ll * C(n * 2, n) % mod * inv[n + 1] % mod;
}

---

最后更新: September 14, 2023