P9174 [COCI 2022/2023 #4] Bojanje 题解

williamwei · 2025-06-14 18:02:46 · 题解

一个目前是最优解，且异于其它任何题解的解法，在未卡常的情况下 15ms。

设 f[n][k] 为 n 次操作后还剩 k 种颜色的概率。

操作后合并颜色，概率是 \dfrac{k(k-1)}{n^2}。

操作后不合并颜色，概率是 1-\dfrac{k(k-1)}{n^2}。

所以 f[n][k]=f[n - 1][k + 1] \times \dfrac{k(k-1)}{n^2} + f[n - 1][k] \times (1-\dfrac{k(k-1)}{n^2})。

用矩阵快速幂优化 DP 即可，将矩阵 A 的第 k 行 k 列设为 1-\dfrac{k(k-1)}{n^2}，第 k 行 k-1 列设为 \dfrac{k(k-1)}{n^2}，计算这个矩阵的 T 次方 B = A^T。

答案为从 n 个颜色经过 T 次操作后仍大于等于 k 个颜色的方案数 \sum \limits_{i=k}^n B_{n,i}。

这道题真的那么简单吗？

不难发现，\dfrac{k(k-1)}{n^2} 这个概率式子随便举一个例子就是错的，例如一个幅颜色为 1 1 4 5 1 4 的画，这里有 3 种颜色，用这个公式算出的概率是 \dfrac{3 \times 2}{6^2} = \dfrac{1}{6}，但实际上只有在选择 i\neq 4 与 j = 4 时才会使得颜色总数减一，概率为 \dfrac{5}{36}，和公式结果不符。

为什么算出来的内容和实际结果不一样呢？因为在这里的“概率”指的是概率的期望，即所有情况下的概率平均值。

用只维护颜色的数量得到的结果乘上所有情况下的概率平均值，从而得到的概率，等价于取所有情况下的结果乘以对应概率的平均值。

现在就可以试图证明 \dfrac{k(k-1)}{n^2} 这个概率的正确性了，先给这些颜色打上标号 1 \sim k，而不是 1 \sim n，再忽略颜色的排列状态，例如 1 1 4 和 4 1 1 等价，这样不会出现问题，因为现在在算概率的期望，此处概率的期望等于概率总和除以总数。

考虑钦定恰好有 i 个颜色在画种恰好出现 1 次。

对于每个 i，先在 k 个颜色中选出 i 个颜色，再确定剩下的颜色的方案数，此时为了使颜色减一，第二个选的下标 j 必定是这 i 个颜色之一，第一个下标只要不等于 j 就行，此时概率为 \dfrac{i(n-1)}{n^2}。

关于颜色划分总数和选完 i 个颜色后的方案数，使用插板法，颜色划分总数相当于在 n-1 个位置中间插 k-1 个板，计算方案数时要注意不能再让某个颜色只出现一次，所以对剩下的 k-i 个颜色都默认已经出现 1 次，再转换为 n-k-1 个位置插 k-i-1 个板的问题。据此推出公式：

在这里可能会出现 n=k 的情况，导致组合数未定义，因为 n=k 时就是 n 个不同的数，使得颜色个数发生变化只要选任意两个不同的下标即可，概率为 \dfrac{n(n - 1)}{n^2}，等于公式，下文只讨论 n>k 情况。

将里面的常数提出来，变成：

要证这个式子等于 \dfrac{k(k-1)}{n^2}，列出等式：

两边同乘 n^2，把左边的 \dbinom{n-1}{k-1} 乘到右边，n-1 除到右边，变为证：

考虑左侧求和部分：

利用恒等式 i\dbinom{k}{i}=k\dbinom{k-1}{i-1}，代入后变为：

此时将这个式子和等式右侧同除 k，令 j=i-1，左侧式等于：

令 a=k-1, b=n-k-1，求和内容变为：

利用 Vandermonde 恒等式的变形，

带入左侧式：

恰好在非 0 的求和范围之内。因为 a=k-1, b=n-k-1，所以左侧式等于 \dbinom{n-2}{k-2}。

变为证明：\dbinom{n-2}{k-2} = \dfrac{k-1}{n}\dbinom{n-1}{k-1}