2023.5 杂题记录

2023.5.18 开始记的。

一道校赛的题（Easy，概率期望 DP）

题目链接。

有一个长度为 \(n\) 的字符串 \(s\)，\(s_i\) 为 o、x、? 中的一个。每个 ? 都等概率替换成 o 或 x。设填完之后 o 连续段长度为 \(a_1,a_2,\cdots,a_m\)，则对于 \(k=1,2,3\)，总贡献为 \(\sum_{i=1}^ma_i^k\)，对 \(k=1,2,3\) 分别求期望总贡献。\(n\leq 3\times 10^5\)。

对 \(k=1\) 是简单的，设 \(p_i\) 为 \(s_i\) 最终为 o 的期望，则：

对 \(k=1\) 答案为 \(\sum p_i\)。