笑了，题做太多导致的。
首先拿到这个题的时候考虑的就是算每个点的期望和，但是这样其实不太好算。
先容易 dp 出 \(f_i\) 表示 \(i\) 个洞走完之后均不影响到更右边/左边的概率，这样就可以算出如果一个点原来就是左脚印，左右都不影响到它的概率。
然后考虑最后答案的形式，一定是某两个点中间没有操作过，左边是左脚印，右边是右脚印，那么枚举这个分界点就可以计算贡献了。
时间复杂度 \(O(n)\)。
ARC132E Paw
发布时间 2023-10-11 08:03:25作者: 275307894a