草，到现在才知道概率期望 DP 这样一个科技啊……
与其它 DP 不同的是，概率期望 DP 往往是列出有后效性的转移式，然后根据概率期望的客观确定性，解出这个方程组从而得到所有 DP 值。我以前只会暴列无穷级数，现在知道自己 sb 了吧……知道这个事情后，我们来做这一题。
首先考虑原状态的最优方案。你每次肯定要熄灭最大的那个灯，而且肯定不要额外开更大的灯吧，所以每部一定是按下当前最大的灯的编号的开关。随便模拟一下就能出来。（所以 B 君为啥觉得难呢）
然后我们考虑随便按上去一个按钮后，剩下来的情况的最优解是什么样的。如果恰好按到原计划的话，由于这个操作是有交换律的，所以最优解就是去掉它。否则如果按到了不该按的，不难知道就是在原最优解中加上它以还原。
于是问题就转化成：当前有 (x) 个计划，你每次随机一个值，要减到 (m) 个计划的期望次数。（(x<m) 直接输出就可以了吧？）
这时候考虑期望 DP。然而我还是走向了歧途。我考虑的是设 (f_i(igeq m)) 为 (i) 减到 (m) 的期望次数。容易知道 (f_m=0)，转移为 (f_i=1+dfrac inf_{i-1}+left(1-dfrac in ight)f_{i+1})。这个怎么解呢？考虑从 (i=m+1) 往上代入消元，每次求出 (f_i) 关于 (f_{i+1}) 的表达式（记录常数项和一次项）。然后发现 (f_n) 只和 (f_{n-1}) 有关，然后结合 (f_{n-1}) 关于 (f_n) 的表达式解出来然后倒推。容易发现每一步的分母都是 (in(0,1]) 的，不用担心 (=0) 的问题。但是问题来了，这里面不仅有乘法，还掺着加法，而分目与一次项有关，有可能 (mod p=0)！这时候已经不可做了。
于是只能参照题解搞出一个分母必定不为 (0) 的更神仙的做法。考虑设 (f_i(i>m)) 为 (i o i-1) 的期望步数（统计答案就全加起来即可），那么容易得到 (f_n=1)，转移 (f_i=1+left(1-dfrac in ight)(f_{i+1}+f_i))。考虑从 (i=n-1downarrow) 倒推，这样分母是 (i)，不可能是 (0)，就可以做了。