初始时你有\(0\)元钱和\(n\)次机会，每次你可以进行两种选择：
\(1.\)退出：拿着现在有的所有钱走人。
\(2.\)继续：此时有\(p\)的概率可以获得\(1\)元钱，有\(1-p\)的概率失去现在有的所有钱并消耗一次机会。
当剩余机会为\(0\)的时候游戏强制结束。
求在最大化期望收益的策略下的期望收益，不考虑精度误差。
\(1\le n\le5*10^6\)
首先考虑\(n=1\)的情况。
很显然我们此时的策略是这样的：一直继续，直到当前手上有\(p_1\)的钱就退出。
那么我们要计算的就是\(f_1(x)=p^xx(x\in\mathbb N)\)的最大值。
\(\Delta f_1(x)=p^x(px+p-x)\)
很显然\(\Delta f_1(x)\)是一个单调递减的函数，因此我们可以直接求出它的零点为\(t=\frac p{1-p}\)。
由此得出\(p_1=\lceil t\rceil\)，期望收益\(s_1=f_1(p_1)\)。
然后考虑\(n=i\)的情况，那么我们此时的策略与\(n=1\)的时候是非常相似的：一直继续，直到当前手上有\(p_i\)的钱就退出。
注意到如果我们失去了所有的钱，那么我们将递归进入\(n=i-1\)的情况，此时的期望收益为\(s_{i-1}\)。
那么我们要计算的就是\(f_i(x)=p^xx+(1-p^x)s_{i-1}(x\in\mathbb N)\)的最大值。
类似于\(n=1\)的情况，\(\Delta f_i(x)\)仍是一个单调递减的函数，因此我们可以直接求出它的零点为\(s_{i-1}+t\)。
由此得出\(p_i=\lceil t+s_{i-1}\rceil,s_i=f_i(p_i)\)。
这样我们就可以递推得到\(s_n\)了。
时间复杂度为\(O(n\log n)\)，其中\(\log n\)为计算快速幂的复杂度。
原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12300487.html