想写但想不起来写啥?
orz 宝爷
orz ?
\(\tt Beautiful\ Mirrors[5.0|B^x]\)
以下默认 \(p_i \leftarrow \dfrac{p_i}{100}\)
显然有转移方程
\[\Large f_i=p_i\times f_{i+1}+(1-p_i)\times f_1+1
\]
令 \(f_i=g(i)\times f_1\)，带入式子：
\[\Large g(i)\times f_1=p_i\times g(i+1)\times f_{1}+(1-p_i)\times f_1+1
\]
\[\Large g(i+1)=\dfrac{g(i)+p_i-1-\frac{1}{f_1}}{p_i}
\]
怎么还有 \(f_1\) 啊。?
令 \(\dfrac{1}{f_1}=x\)，所有的 \(g(i)\) 都可以表示成 \(k_i\times x+b_i\) 的形式。
用一个结构体维护一下即可。
有 \(g(1)=1(k_i=0,b_i=1)\)，可以递归求所有 \(g(i)\)。
有 \(g(n+1)=f_{n+1}=0\)，可以解出 \(x=-\dfrac{b_{n+1}}{k_{n+1}}\)。
\(f_n={k_nx+b_n}\) 即为答案。
还有这博客的公式大小锅的这么明显 ???