暑训5-L 题意 有  个格子，起点位于  号格子，终点是  号格子；你有若干硬币，对于非终点的格子，每走一步，有  的概率成功走到下一个格子，否则尝试消耗  个硬币留在原地，若无硬币则回到起点。求对于每个初始硬币数  ,你从起点走到终点所需的期望步数。 解：期望dp 如果你对公式感到困惑可以看看转移图：  这里的方向是实际模拟时状态改变的方向，但推期望的时候是反过来推的。 我们设  为剩余  个硬币，在第  个格子时步数的期望。 对于第  层我们有：  暴力消元可以解出  ，然后暴力回代得：  对于其他层有：  又设差分：  对  作差分可得：  计算  :  考虑  对  的总贡献：不妨想...