原创，但是典题

考虑设 $f_i$ 为加载出 $i$ 格所需的期望时间，那么有：

$f_i=(1-P) \times \Big[(f_{i-1}+1)+P(2f_{i-1}+2)+P^2(3f_{i-1}+3)+ \dots \Big]$

化简得

$f_i=(1-P)(f_{i-1}+1) \sum_{i=0}^{\infty } (i+1)P^i$

由于 $\sum_{i=0}^{\infty } (i+1)P^i=\frac{1}{(1-P)^2}$，所以 $f_i=\frac{f_{i-1}+1}{1-P}$。

$f_0=0$，归纳得 $f_N=\sum_{i=1}^{N} \frac{1}{(1-P)^i}$，求和并化简得 $f_N=\frac{1-(1-P)^N}{P(1-P)^N}$。

因此可以用快速幂以 O(logN) 的复杂度解决本题。