解题报告-论对“期望”的理解

致敬传奇期望王

这道题我写了 \(5\) 遍，每遍都没有思路，都是看题解或者自己之前的代码才写出来的。现在这里做一个这道题的总结，防止以后再出现这种情况。

首先，这题看起来就很线性，但是我们不能一上来就 \(f_i\) 表示前 \(i\) 个点的分数期望，会发现很难转移。

第一步：剖析题面。这道题的题意很清楚，性质也很明白，只有连续的段才能够贡献分数。所以我们设 \(f_i\) 表示以 \(i\) 结尾的段的期望分数。那么只用统计打出的结果为 \(1\) 的情况，因为 \(0\) 是无意义的。这是卡我的第一个点：想一步推完。

第二步：考虑转移。设在 \(i-1\) 处有一个长度为 \(x\) 的连续段，那么在 \(i\) 处就会有 \(p_i\) 的概率出现一个长度为 \((x+1)\) 的连续段。那么，如果我们要由 \(i-1\) 的分数转移而来，很明显要加上 \(3x^2+3x+1\)。所以，设 \(f_{1,i}\) 表示以 \(i\) 结尾的段的期望长度，\(f_{2,i}\) 表示以 \(i\) 结尾的段的期望长度的平方，\(f_{3,i}\) 表示以 \(i\) 结尾的段的期望分数。那么 \(f_{1,i}=f_{1,i-1}\times p_{i},f_{2,i}=f_{2,i-1}+2f_{1,i-1}+1,f_{3,i}=f_{3,i-1}+3f_{2,i-1}+3f_{1,i-1}+1\)。这里，推导是分两步的，但是如果我们想要一步推完，那就真的是难于上青天。这是卡我的第二个点：想一步推完。

第三步：统计答案。答案肯定不等于 \(\sum f_i\)，但是我的第一个思路就假在这里，我一直想怎么直接用 \(f\) 得到答案。。我们一步一步来，如果我们把答案拆成一堆增长量，也即 \(f_{i-1}\) 转移到 \(f_i\) 时增加的部分呢？那就很赏心悦目了：\(ans_i\) 表示期望的增长量，那么答案等于 \(\sum ans_i\)。这是卡我的第三个点：想一步推完。

综上所述，遇到这种题一定要一步一步推，可以多设变量，对了就行，一定不要拘泥于原来几个变量，也一定不要认为只用几个变量就可以推出来！