CF1778D - Flexible String Revisit 题解

标签：frac CF1778D 题解 Revisit Flexible 匹配 dp

CF1778D - Flexible String Revisit

题面

给出两个长度均为 \(n(n\leq 10^6)\) 的 01 串 \(S\) 和 \(T\)

每次随机将 \(S\) 中的某一位取反

问：第一次 \(S = T\) 时操作次数的期望

---

题解

成环期望的小 \(\text{trick}\)，可以避免高斯消元和高阶递推。

如果我们按照经典的期望 \(dp\) 来设 \(f_i\) 表示当前还有 \(i\) 个字符未匹配：

\[f_i = \begin{cases} \frac{1}{n} f_1 + 1 & i = 0 \\ \frac{n - i + 1}{n} f_{i - 1} + \frac{i + 1}{n} f_{i + 1} + 1 & i \in [1, n) \\ \frac{n - 1}{n} f_{n - 1} + 1 & i = n \end{cases} \]

必须要使用二阶递推求系数或者建立系数矩阵进行高斯消元，我们不妨从定义上去改变原有的式子，使得关系式只与一项相关，考虑如下定义：

设 \(f_i\) 表示只剩下 \(i\) 个字符未匹配且本次操作使得一个位匹配的期望操作次数。

由此定义的 \(f_i\) 仅由 \(f_i\) 本身和 \(f_{i + 1}\) 决定，自己匹配的概率是 \(\frac{i}{n}\)，否则会取消一个位的匹配，既然取消了我们必须将他翻转回来，这就和 \(dp_{i + 1}\) 相关。

可以列出式子 \(dp_i = \frac{i}{n} + \frac{n - i}{n}(dp_i + dp_{i + 1} + 1)\)，化简可得：

\[dp_i = \frac{n}{i} + \frac{n - i}{i}dp_{i + 1} \]

设初始状态未匹配的个数为 \(x\)，我们只需求出 \(\sum\limits_{i = 1}^{x}dp_i\) 即可。

参考代码

标签：frac,CF1778D,题解,Revisit,Flexible,匹配,dp
From： https://www.cnblogs.com/YipChipqwq/p/-/CF1778D