题解：AT_arc174_c [ARC174C] Catastrophic Roulette
__ryp__
·
·
题解
和机房 dalao 在机房黑板上推了式子，但是不如队爷 cxm 的简洁，替他 写个题解。
这题和百事世界杯那道很像，区别就是这题是有两个人的。
但是状态是一样的。
我们设 f(x) 表示作为先手，当前有 x 个物品已经被摸到的期望代价，同理设 g(x) 代表后手的相应情况。（用 i 做变量的话推式子老觉得跟复分析一样qwq）
对于每一次摸球，我们只有摸到新的和摸到旧的两种可能。
- 摸到新的，概率是 \dfrac {n - x} n，此时有
f(x) = g(x + 1), \\
g(x) = f(x + 1)
\end{cases}
f(x) = g(x) + 1, \\
g(x) = f(x)
\end{cases}
这个先后手的转移有一点抽象。当前的先手，转移之后自然是后手，反之亦然。这里玩家并没有改变，仍然是 A 和 B，只是先后手的顺序改变了。我们用状态，用的就是它的语义。
联立这个方程，得到解：
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}
倒着递推就行了。