随机游走专题：https://www.cnblogs.com/NY2025/p/18958112
线性基计数专题：https://www.cnblogs.com/NY2025/p/18973300
这俩 jzp 之前没布置过，自己瞎琢磨的。但是忘完了。
随机事件概率期望
P3750 [六省联考 2017] 分手是祝愿
Informatik verbindet dich und mich. 信息将你我连结。
Zeit und Raum trennen dich und mich. 时空将你我分开。
感觉是很简单的题呢。
按多次的情况等价于不按或只按一次，将每个键按或不按构成的 0-1 序列称为策略，要找到达到最终状态的策略可以直接模拟做一次异或高斯消元。
这个模拟异或高斯消元的过程事实上就是从后往前扫描，碰到一个亮着的灯就将按钮标记为必须按，可以发现要使所有灯灭掉的策略是唯一的。
设 \(f_i\) 为从当前存在 \(i\) 个必须按的键转移到存在 \(i-1\) 个所需的期望操作数，此时有：
\[f_i=\frac{i}{n}+\frac{n-i}{n}\cdot(f_i+f_{i+1}+1)
\]
\(f_i+f_{i+1}+1\) 的意思是：按到一个错误的键，贡献为 \(1\)；需要把这个错误的键按一次归位，此时有 \(i+1\) 个需要按的键，贡献为 \(f_{i+1}\)；要继续按键转移到 \(i-1\)，贡献为 \(f_i\)。
然后把这个式子看作 \(f_i\) 的方程，将所有 \(f_i\) 项移到左边得：
\[\begin{align*}
\frac{i}{n}\cdot f_i&=\frac{n+(n-i)\cdot f_{i+1}}{n}\\
f_i&=\frac{n+(n-i)\cdot f_{i+1}}{i}
\end{align*}
\]
（这玩意题解区有人用 band-matrix 优化，本质是一样的，但谁正常人拿着只有两个参数的方程高斯消元啊？）
最终答案为\(\sum_{i=k+1}^{tot}f_i\)，其中 \(tot\) 为必须按的按键数量。