QOJ17256 Keep or Gamble 题解

本质推式子题目。

不妨考虑什么时候应该停止，什么时候应该继续往下走。

不妨将四种卡片分别记作 。 分别表示分数是 的卡片， 表示直接结束游戏的卡片。

首先一个观察是 卡片没有用。不妨考虑暴力 DP，枚举下一种可能。你可以将“第一次抛的结果”替换成”第一次抛到非 卡片的概率“，这样就变成了一个条件概率，并且这个条件概率和剩下的 卡片数量无关。

另外一个观察就是 的卡片在没有被淘汰的时候一定是 张。

因此我们只需要记录当前抽了几张 卡片几张 卡片即可。因此我们有一个简单的 的 DP。当后续状态可以带来的增量为负时，我们就应该停下来。

但是这个 DP 其实没什么常规手段去优化，我们得想一些更强的性质。

我们不妨放弃考虑后续所有状态的增量，转而考虑单步的增量。假设你有了 张 卡片和 张 卡片。

令 ，我们有 的概率抽到 ， 的概率抽到 ， 的概率直接输掉，失去所有钱，获得 。

那么，此时你单次期望的收益就是这个式子：

那么，看上去如果这个值为负，那么这一步就是亏的。

但是，有没有可能后续会带来更大的收益呢？

实际上也不可能。如果此时你抽了一张 或者 ，那么其中的每个值都会变小，因此一旦一个状态单步为负，后续所有状态都是负的。

因此，一旦单步期望变成负的，我们就应该直接卷款跑路！

进一步的，我们可以得到这个式子：

其中， 表示所有抽出来 张 卡片和 张 卡片的方案数， 表示所有卡片中抽出来 张卡片的概率。 满足 。

简单解一下右侧的不等式，就可以得到 。

我们希望用低于 的复杂度进行计算。因此我们不妨随便枚举一点东西，然后推一下式子。

注意到式子里有大量的 ，不妨令 ，做变量代换。

提出来和内层变量 无关的项。

我们主要关注右侧第二个求和号的计算。

括号全部展开。

拆拆拆。

先看左边。

里面和 全部无关。因此全部提出来。

我们实际上要计算的是这个。

请注意，这个虽然看上去很像范德蒙德卷积，但是实际上不是。

因为我们的下标没写全。下标需要满足 。令 ，代换之后也就是 。也就是 。

换句话说求和号是有下界的。因此并不能直接范德蒙德卷积。

接下来考虑右侧。

提取公因式。

无关项提出来。

实际上我们要计算

请注意

因此实际上我们要计算

令

对于 ，求和下界是 。实际上等号取等与否无所谓，因此从 开始求和也是可以的。

注意到当 增加的时候，求和下界实际上增加的并不多。因此我们如果能从 推到 ，那么我们只需要手动减去 项就可以用来计算 时候的答案了。

我们目前的首要目标就是通过 推出来 。

推出来 是容易的。因为我们有

因此

因此我们可以直接用 减掉 ，有

而

做 代换。

和我们刚刚推出来的式子只有下标变换了 。手动处理一下这几项即可。

难办的是 。

对称的，我们考虑

在前一项组合数两个都减少 的情况。 的递推和 类似，这里不再赘述。

我们考虑我们最初的形式：

实际上是，

我们希望消掉右侧的 。此时我们的 就可以派上用场了。类似的，我们有

也就是

我们将两项相加，得到

因此，我们推出 之后，可以使用 来推出 。

综上，式子里的所有部分都是可以递推的了。

代码反正能写。之后补上。