战忽局的手段
$Description$
$Solution$
套路题。
根据期望的线性,我们可以设 $f_i$ 表示 $m$ 次演讲忽悠成了 $i$ 次的概率。
$$
Ans = \sum f_i
$$
$$
f_i = f_{i - 1} + (1 - \frac{ f_{i - 1} }{n})
$$
忽悠成 $i - 1$ 次,有 $\dfrac{f_{i - 1}}{n}$ 的概率书被拿过,会失败。
化简就是
$$
f_i = \frac{n - 1}{n} f_{i - 1} + 1
$$
上个矩阵优化一下就是 $\Theta(T \log\ n)$ 的了。
转移矩阵就是
$$
\begin{bmatrix}
\frac{n - 1}{n} & 1
\\
0 & 0
\end{bmatrix}
$$
注意精度,要用 $float128$ ,毒瘤。
$Code:$
1 |
|