【题解】YZOJ5037 升级

HMF-have much fun Site

文章标签

载入天数...

载入时分秒...

总访问量: | 访问人数:

阅

2022-03-25

3 min read

YZOJ 题解

给一个非常愚蠢的推式子：

设 $d_i$ 为从第 $i-1$ 级升到第 $i$ 级所需的期望步数， $P$ 为每次升级成功概率， $Q$ 为每次升级失败概率（ $P+Q=1$ ）。

推 $d_n$ ，设 $p_i$ 为第 $i$ 次试图从 $n-1$ 级升到 $n$ 级时成功的概率， $s_i$ 为则为其所需的步数。

同时设 $\alpha = d_{n-a}+d_{n-a+1}+...+d_{n-1}$ ，则

$s_i=(i-1)\times\alpha+i , p_i=Q^{i-1}P$

$d_n=s_1\times p_1+s_2 \times p_2+ ... + s_∞ \times p_∞$

由于 $p_i \le 1$ ，具有收敛性：

$d_n=P + (\alpha + 2)PQ+(2\alpha+3)PQ^2+(3\alpha+4)PQ^3+......$

$Q\times d_n = PQ + (\alpha + 2)PQ^2+(2\alpha+3)PQ^3+(3\alpha+4)PQ^4+......$

$(1-Q)d_n = P+P(\alpha+1)(Q+Q^2+Q^3+Q^4+...)=P+P(\alpha+1) \frac{Q}{P}$

$d_n=1+(\alpha+1)\frac{Q}{P}=1+\frac{Q}{P}+\alpha\frac{Q}{P}$

设 $f_n$ 为从 $0$ 级升到 $n$ 级所需要的步数

$f_n=\sum_{i=1}^nd_i$

$f_n=n+n\frac{Q}{P}+\frac{Q}{P}(\sum_{i=n-a}^{n-1}f_i)$

构造矩阵转移即可。

赏