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 的期望，则：
\[p_i=\begin{cases}1&s_i=\text{o}\\0&s_i=\text{x}\\0.5&s_i=\text{?}\end{cases}
\]
对 \(k=1\) 答案为 \(\sum p_i\)。
设 \(g(i,0)\) 表示位置 \(i\) 所处连续段的期望连续长度（若 \(s_i=\text{x}\)，则 \(g(i,0)=0\)），则：
\[g(i,0)=(g(i-1,0)+1)\cdot p_i
\]
设 \(f(i,1)\) 表示到位置 \(i\)，\(k=2\) 时的期望答案，\(i\) 的贡献为 \(2x+1\)（\(x\) 为之前连续的长度），则：
\[f(i,1)=f(i-1,1)+(2g(i-1,0)+1)\cdot p_i
\]
答案为 \(f(n,1)\)。
同理设 \(f(i,2)\) 和 \(g(i,1)\)，得：
\[g(i,1)=(g(i-1,1)+2g(i-1,0)+1)\cdot p_i
f(i,2)=f(i-1,2)+(3g(i-1,1)+3g(i-1,0)+1)\cdot p_i
\]
答案为 \(f(n,2)\)。总时间复杂度 \(O(n)\)