这种可能会有无穷的情况，就是对某一个开关一直按
像这种题目我把他叫做无穷型嵌套期望
这种题目一般都是用DP推出公式然后化简
看着题
首先，我们考虑假设最开始最少的操作少于k，应该怎么做
很容易发现一个性质，就是按动一个开关，只能影响前面的开关，不能影响后面的开关
这是什么？无后效性！就跟DP一样，我们以后遇到这种情况，就要从前往后（这题是从后往前）考虑
我们从后往前考虑（因为这题很显然每个开关最多按一次，而且按得顺序没有关系），假设对当前考虑的这个开关，后面的开关的按动情况都已经决定了，那么是否按当前这个开关只用看他是否开即可。然后一个序列的操作就是唯一的
那如果这个唯一的操作比k大怎么办？
为了行文方便，我们规定对一个序列，0表示不按动，1表示按动
首先，这里是完全随机地按动开关
意味着对多个序列，这些序列1的个数（大于k）相同，他们到达只有k个1的期望步数是相同的（相当于这些序列是“完全等价”的，可以都把这些序列想象成前面全是0后面全是1，很显然是相同的步数）
所以我们设f[i]表示从i个1走到k个1的期望步数
注意，这是这类题非常重要的一个性质。因为有i个1的序列太多太多了，我们要想用一个f[i]表示，那么一定要保证每种情况的f[i]是相同的。其他嵌套期望类似
于是有\(f[i]=\frac{i}{n}f[i-1]+\frac{n-i}{n}f[i+1]+1\)
注意这是第二个性质，在写公式的时候，一定不要让f[i]同时需要两个方向的f，因为这两个方向的f同样需要f[i]，是没办法递推的
这里我们换一个状态，设f[i]表示从i个1变成i-1个1的期望步数
然后剩下看洛谷题解吧
标签：洛谷,相同,开关,3750,祝愿,按动,序列,期望,步数 From： https://www.cnblogs.com/dingxingdi/p/17736304.html