AC. 梦想

frank_c1

[ZJOI 2013] 抛硬币

发布于2017年03月01日 | 暂无评论 | 573阅读 | 动态规划,递推,高精度

题意简述

有一枚硬币,抛出正面的概率是\frac{a} {b},反面的概率就是1 - \frac{a} {b}

现在给定一个硬币序列S(正面/反面)。现在开始连续抛硬币,当某一枚硬币抛完后,若S作为一段连续子序列出现在了抛出的硬币序列中,则停止。

求到停止的期望步数。输出一个最简分数。

1 \le |S| \le 1000, 1 \le a \le b \le 100

算法讨论

题目已经给出了一个相当正确的思路,继续往下走就好啦。

我们考虑抛硬币的过程,相当于是一个匹配的过程,如果某一个位置匹配失败,我们考虑转移到它的失配位置继续走。

这是一个自动机上的概率转移模型。设一个点的失配位置是G_i,有如下方程。

对于0 \le i \le |S| - 1E[i] = P(succ_i) E[i+1] + P(fail_i) E[G_i] + 1。对于i = |S|E[i] = 0

直接高斯消元是是O(n ^ 3)的,由于矩阵特殊,可以优化到O(n ^ 2)

所以我们解决了这个问题吗?如果出题人要求在模意义下可能就过了……

由于答案位数和n同阶,上面的算法都必须乘上高精度运算的复杂度,不可通过。

我们换个视角看看。

E[i+1] = \frac{E[i] - P(fail_i) E[G_i] - 1} {P(succ_i)}

这就是个递推啊。但是我们不知道E[0]的值呀。不妨设E[i] = K_i E[0] - C_i,推到E[n]0会合不就天下太平了。

时间复杂度O(np),其中p是答案位数。

(小小的吐槽:我程序的80%都是高精度,这是不是有点偏离了考察点啊??