自动搬运

查看原文

来自洛谷，原作者为

	williamwei 经典不流传

搬运于2025-08-24 22:46:02，当前版本为作者最后更新于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$ 个板的问题。据此推出公式：

$$\frac{1}{\binom{n-1}{k-1}}\sum \limits_{i=1}^{k-1} \dfrac{i(n-1)}{n^2}\dbinom{k}{i}\dbinom{n-k-1}{k-i-1} $$

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

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

$$\frac{n-1}{n^2\binom{n-1}{k-1}}\sum \limits_{i=1}^{k-1} i\dbinom{k}{i}\dbinom{n-k-1}{k-i-1} $$

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

$$\frac{n-1}{n^2\binom{n-1}{k-1}}\sum \limits_{i=1}^{k-1} i\dbinom{k}{i}\dbinom{n-k-1}{k-i-1} = \dfrac{k(k-1)}{n^2} $$

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

$$\sum \limits_{i=1}^{k-1} i\dbinom{k}{i}\dbinom{n-k-1}{k-i-1} = \dfrac{k(k-1)}{n}\dbinom{n-1}{k-1} $$

考虑左侧求和部分：

$$\sum \limits_{i=1}^{k-1} i\dbinom{k}{i}\dbinom{n-k-1}{k-i-1} $$

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

$$k \sum \limits_{i=1}^{k-1}\dbinom{k-1}{i-1}\dbinom{n-k-1}{k-i-1} $$

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

$$\sum \limits_{j=0}^{k - 2}\dbinom{k-1}{j}\dbinom{n-k-1}{k-j-2} $$

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

$$\sum \limits_{j = 0}^{k - 2}\dbinom{a}{j}\dbinom{b}{a-j-1} $$

利用 Vandermonde 恒等式的变形，

$$\sum \limits_{j} \dbinom{a}{j}\dbinom{b}{c-j}=\dbinom{a+b}{c} $$

带入左侧式：

$$\sum \limits_{j=0}^{a-1}\dbinom{a}{j}\dbinom{b}{(a-1)-j}=\dbinom{a+b}{a-1} $$

恰好在非 $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}$

$k<2$ 时由于未定义需要单独考虑，先考虑 $k \geq 2$ 情况，将左右侧展开，左侧式子为：

$$\dbinom{n-2}{k-2} = \dfrac{(n-2)!}{(k-2)!(n-k)!}$$

右侧式子为：

$$\dfrac{k-1}{n}\dbinom{n-1}{k-1} = \dfrac{(k-1)(n-1)!}{(n-1)(k-1)!(n-k)!}=\dfrac{(n-2)!}{(k-2)!(n-k)!} $$

两侧式子相等。

考虑 $k<2$ 情况，即 $k=1$，左侧求和范围为 $1 \sim 0$，所以左侧式子为 $0$，右侧内容也为 $0$，证毕。