本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-21 15:05:14

和机房 dalao 在机房黑板上推了式子，但是不如队爷 cxm 的简洁，替他 写个题解。

这题和百事世界杯那道很像，区别就是这题是有两个人的。 但是状态是一样的。

我们设 $f(x)$ 表示作为先手，当前有 $x$ 个物品已经被摸到的期望代价，同理设 $g(x)$ 代表后手的相应情况。（用 $i$ 做变量的话推式子老觉得跟复分析一样qwq）

对于每一次摸球，我们只有摸到新的和摸到旧的两种可能。

• 摸到新的，概率是 $\dfrac {n - x} n$，此时有

$$\begin{cases} f(x) = g(x + 1), \ g(x) = f(x + 1) \end{cases}$$

• 摸到旧的，概率是 $\dfrac x n$，此时

$$\begin{cases} f(x) = g(x) + 1, \ g(x) = f(x) \end{cases}$$

这个先后手的转移有一点抽象。当前的先手，转移之后自然是后手，反之亦然。这里玩家并没有改变，仍然是 A 和 B，只是先后手的顺序改变了。我们用状态，用的就是它的语义。

联立这个方程，得到解：

$$\begin{cases} f(x) = \bigg(\dfrac {n - x} n \cdot g(x + 1) + \dfrac{x\cdot (n - x)}n \cdot f(x + 1) + \dfrac x n\bigg) \bigg/ \bigg(1 - \dfrac {x^2}{n^2}\bigg) \ g(x) = \dfrac x n \cdot f(x) + \dfrac{n - x}n \cdot f(x + 1) \end{cases}$$

倒着递推就行了。