This problem has only Japanese editorials and Youtube videos.
People in mainland China are not allowed to visit youtube (VPN or similar is illegal) and I'm not studying Japanese (the translation is terrible), so can anyone translate or just post the written editorial here?
鲜花链接
感觉肯定比 G 难吧
首先因为这个庄家像个波特一样只会往上垒 我们可以容易算出庄家最后的数是 $$$i$$$ 的可能性 记其为 $$$w_i$$$ 类似地 我们可以算出我们在一直拿 可以停的情况下 最后的数是 $$$i$$$ 的可能性 记其为 $$$u_i$$$ 这两个计算很简单 略过
然后就是好玩的 dp 部分 我们倒序 dp 可以选择不掷了 或者掷一次骰子 取 $$$\max$$$ 那么就是
然后对于所有的 dp 取 $$$\max$$$ 这样就行了吗 不 因为你很难让他停在 $$$x$$$ 他可能会往后高达 $$$(d-1)$$$ 个 因此发现我们缺的部分的答案为
其中 $$$t_i=\dfrac{1-w_i}d$$$。
其实就是他们到了就不取了 然后乘的两项分别为到他们的概率和赢得概率 这样我们三个前缀和处理一下上式就行了 可以见代码
然后就做完了 发现还可以去掉 dp 我们发现这个 dp 也是掷或不掷骰子取最大值 而不掷骰子的情况已经被包含在上面了 所以我们直接把上式的 $$$x-1$$$
改成 $$$x$$$ 就成答案了 就是这样还是用三个前缀和 维护就行了
为了让 cf 的渲染器不出锅 删掉了所有标点 :D
He is my classmate so I'm sure he is Chinese (:
Thanks! Das ist sehr nett von dir.