自动搬运

查看原文

来自洛谷，原作者为

	lzyqwq 我永远喜欢数据结构。

搬运于2025-08-24 23:02:01，当前版本为作者最后更新于2024-08-11 18:26:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小 L 是一个机器人，负责协助老 L 的研究工作。

老 L 在生命的最后时刻在研究一种奇怪的生物 L。这种生物的遗传遵循融合遗传规律。老 L 在一定的空间里让它们自由交配。

已知一共有 $n$ 个 L 个体，第 $i$ 个 L 个体有一个能力值 $a_i$。这些 L 个体会进行 $n-1$ 轮交配。每次交配会 等概率随机 选出当前存在的两个 L 个体 $x,y$，然后它们会繁衍出一个子代，能力值为 $\dfrac{a_x+a_y}{2}$，最后 $x,y$ 两个个体会死亡。子代可以继续参与后续的交配。显然最后只会剩下一个 L 个体，求它的 期望 能力值 $E(a)$。

老 L 已经进行了多次交配实验，但是仍然无法得到理想的结果。他需要小 L 进行更精密地计算。

小 L 选取了 $3$ 个 L 个体，能力值分别为 $a=(1,2,4)$，然后开始了演算。

如果第 $1$ 轮交配选取 $1,2$ 两个 L 个体，则会得到能力值为 $\dfrac{3}{2}$ 的子代；第 $2$ 轮由剩余的两个个体交配，会得到能力值为 $\dfrac{11}{4}$ 的子代。得到这种结果的概率为 $\dfrac{1}{3}$。

同理，剩余两种选取方式得到的最终 L 个体能力值分别为 $\dfrac{9}{4}$ 和 $2$，得到它们的概率均为 $\dfrac{1}{3}$。

最后的 L 个体期望能力值为 $E=\dfrac{9}{4}\times \dfrac{1}{3}+\dfrac{11}{4}\times \dfrac{1}{3}+2\times \dfrac{1}{3}=\dfrac{7}{3}$。

小 L 猛然发现 $E(a)$ 恰好为 $1,2,4$ 的平均数，它不敢相信这个绝望的结果。

小 L 用数学归纳法进行了更严谨的证明。

$\bf{Blending\space\space Inheritance\space\space Theory}$

若 $n$ 个 L 个体的能力值分别为 $(a_1,\dots,a_n)$，则 $E(a)=\dfrac{\sum_{i=1}^n a_i}{n}$。

$\bf{Proof}$

• 当 $n=2$ 时，显然成立。

• 若当 $n=m$ 时成立，则当 $n=m+1$ 时，考虑第一轮交配选取了 $i,j\,(i<j)$ 两个 L 个体，记 $b(i,j)$ 表示 $a$ 序列删除 $a_i,a_j$ 两个元素并插入 $\dfrac{a_i+a_j}{2}$ 这个元素后得到的新序列，即选取 $i,j$ 作为第一轮交配的个体交配后得到的序列。有：

  $$\begin{aligned}E(a)&=\sum\limits_{i=1}^{m}\sum\limits_{j=i+1}^{m+1}\dfrac{2E(b(i,j))}{m(m+1)}\\&=\dfrac{2}{m(m+1)}\sum\limits_{i=1}^m\sum\limits_{j=i+1}^{m+1}\dfrac{\sum_{k=1}^mb(i,j)_k}{m}\\&=\dfrac{2}{m(m+1)}\sum\limits_{i=1}^m\sum\limits_{j=i+1}^{m+1}\dfrac{\left(\sum_{k=1}^{m+1}a_k\right)-\frac{a_i+a_j}{2}}{m}\\&=\dfrac{2}{m^2(m+1)}\sum\limits_{i=1}^m\sum\limits_{j=i+1}^{m+1}\sum\limits_{k=1}^{m+1}a_k-\dfrac{1}{m^2(m+1)}\sum\limits_{i=1}^m\sum\limits_{j=i+1}^{m+1}(a_i+a_j)\\&=\dfrac{2}{m^2(m+1)}\times \dfrac{m(m+1)}{2}\sum\limits_{i=1}^{m+1}a_i-\dfrac{1}{m^2(m+1)}\times m\sum\limits_{i=1}^{m+1}a_i\\&=\dfrac{\sum_{i=1}^{m+1}a_i}{m}-\dfrac{\sum_{i=1}^{m+1}a_i}{m(m+1)}\\&=\dfrac{\sum_{i=1}^{m+1}a_i}{m+1}\end{aligned} $$

• $\mathcal{Q.E.D.}$

小 L 不可置信地看着看着这个无比正确的结论。难道繁衍的意义就是平均。平均。平均。然后死亡。死亡。死亡。然后一无所有。

老 L 看到这个结果，不知道脸上是欢喜还是悲伤，但是他完成了研究 L 生物的任务。然后，他不留遗憾地死了。

真的没留下遗憾吗？老 L 在临死前将自己的记忆芯片植入了小 L 的处理器。小 L 处理器中的数据流向它展示了老 L 的一生。

老 L 在小学的时候成绩还算不错。小升初的暑假他开始学习信息学竞赛。然而学着学着，老 L 的 OI 成绩却平庸。平庸。平庸。whk 成绩也平庸。平庸。平庸。在【】面前也平庸。平庸。平庸。

接着，老 L 的 OI 失败。失败。失败。whk 失败。失败。失败。和【】的距离拉远。拉远。拉远。

……

最后，老 L 除了小 L 和生物 L 之外，一无所有。

小 L 奔溃地大吼，它不敢相信毫无意义的平均。平均。平均。就是世界的意义。小 L 甚至开始嚎啕大哭。

但是小 L 是机器人，它不会哭。它理解不了哭的意义。

但是它会哭。因为哭毫无意义。