日记详情

例题1 单选错位

形式化题意
给定循环序列 \(a_1,\dots,a_n\)，第 \(i\) 道题答案被抄到第 \(i+1\) 题位置（\(a_{n+1}=a_1\)）。每道题正确选项独立均匀取自 \([1,a_i]\)。求做对题数的期望。

思路
由线性期望，只需考虑每道题。第 \(i+1\) 题位置的答案是第 \(i\) 题的正确选项，与第 \(i+1\) 题正确选项独立。两个独立均匀变量分别取自大小为 \(a_i,a_{i+1}\) 的集合，相等的概率为

\[\frac{\min(a_i,a_{i+1})}{a_i a_{i+1}}=\frac1{\max(a_i,a_{i+1})}. \]

所以

\[E=\sum_{i=1}^n \frac1{\max(a_i,a_{i+1})}. \]

按生成器生成数组后 \(O(n)\) 累加即可。

---

例题2 期望分数

形式化题意
给定由 o,x,? 组成的字符串，? 独立等概率变为 o 或 x。分数定义为所有连续 o 段长度的平方和，求期望分数。

思路
从左到右扫描，设 \(L\) 为当前位置之前连续 o 的期望长度。若当前字符为 o 的概率是 \(p\)，则当前位置若为 o，新增贡献为

\[(L+1)^2-L^2=2L+1. \]

因此期望增量贡献为 \(p(2L+1)\)。同时更新期望连续长度：

\[L' = p(L+1). \]

累加所有增量即可，\(O(n)\)。

---

例题3 路径长度

形式化题意
给定有向无环图，起点 \(1\)，终点 \(n\)，每条边有长度。从每个点等概率选择一条出边，求从 \(1\) 到 \(n\) 的期望路径长度。

思路
设 \(f[u]\) 表示从 \(u\) 到 \(n\) 的期望长度，\(f[n]=0\)。若 \(d(u)\) 为 \(u\) 的出度，则

\[f[u]=\frac1{d(u)}\sum_{(u,v,w)}(w+f[v]). \]

按拓扑逆序计算即可。实现时用逆图从 \(n\) 开始反向拓扑，每处理完一条出边就累加到前驱，当某点所有出边都处理完时入队。复杂度 \(O(n+m)\)。

---

2.电影问题

有 \(n\) 部电影，第 \(i\) 部长度为 \(l_i\)，被喜欢的概率 \(p_i=x_i/y_i\)。可自由安排顺序。若喜欢：获得 \(+l_i\) 并收藏；若不喜欢：获得 \(-l_i\)，并重看所有已收藏电影，每部再增加其长度。求最优顺序下的期望总快乐值，对 \(1004535809\) 取模。

1. 总期望的分解
设观影顺序为 \(1,2,\dots,n\)。事件分为两部分：

• 第 \(i\) 部电影自身的即时影响：喜欢则 \(+l_i\)，不喜欢则 \(-l_i\)，贡献期望为

  \[E_i^{self} = p_i l_i + (1-p_i)(-l_i) = (2p_i-1)l_i \]

• 第 \(i\) 部电影不喜欢时触发的“复习”：若第 \(i\) 部不喜欢（概率 \(1-p_i\)），他会把之前所有收藏的电影再看一遍。之前收藏的电影 \(j\) 被收藏的前提是 \(j\) 被喜欢（概率 \(p_j\)），且 \(j\) 的时长是 \(l_j\)。所以这部分额外期望为：

  \[\sum_{j < i} p_j l_j \cdot (1-p_i) \]

将两部分叠加，总期望为：

\[E = \sum_{i=1}^n (2p_i-1)l_i + \sum_{i=1}^n \sum_{j < i} p_j l_j (1-p_i) \]

2. 最优顺序的确定（相邻交换法）
顺序只影响交叉项 \(\sum_{j<i} p_j l_j (1-p_i)\)。
考虑相邻两项 \(i\)（前）和 \(j\)（后）。假设前面已经积累的收藏期望总长为 \(S\)。

• 顺序 \(i \to j\) 时，这两步对总期望的交叉贡献（不含自身项）为：
  \(S(1-p_i)\)（i不喜欢时复习前面的） \(+\ [S + p_i l_i](1-p_j)\)（j不喜欢时复习前面的，包含i若被收藏）
  整理为：\(S(2 - p_i - p_j) + p_i l_i (1-p_j)\)

• 顺序 \(j \to i\) 时，交叉贡献为：
  \(S(1-p_j) + [S + p_j l_j](1-p_i) = S(2 - p_i - p_j) + p_j l_j (1-p_i)\)

消去公共项 \(S(2 - p_i - p_j)\)，\(i\) 排在 \(j\) 前更优当且仅当：

\[p_i l_i (1-p_j) > p_j l_j (1-p_i) \]

移项得：

\[\frac{p_i l_i}{1-p_i} > \frac{p_j l_j}{1-p_j} \]

当 \(p=1\) 时，分母为0，其期望复习价值极大，必须排在所有 \(p<1\) 之前。

---

3.拯救计划

给定 \(n\) 个点的初始无向图，已有 \(m\) 条边，得到若干连通块。每一步等概率从所有无序点对中选一对，若连接不同连通块则合并，否则状态不变。求使整个图连通的期望步数。

1. 状态定义
设当前有 \(k\) 个连通块，大小分别为 \(s_1,\dots,s_k\)，总点数 \(n\)。
总无序点对数（含同一块内和块间）为：

\[T = \binom{n}{2} = \frac{n(n-1)}{2} \]

2. 一步转移的概率

• 选中块 \(i\) 和块 \(j\)（\(i<j\)）之间的点对，会合并这两个块。这样的点对数为 \(s_i \cdot s_j\)，概率为：
  \[p_{ij} = \frac{s_i s_j}{T} \]

• 选中同一块内部的点对，或选中已连通块内的点，状态不发生任何改变（因为图不会变）。这部分概率为：
  \[p_{stay} = 1 - \sum_{i<j} p_{ij} \]

3. 期望方程的建立
设 \(f(S)\) 为当前状态到完全连通的期望步数。
进行一次随机选边后，要么留在原状态，要么跳到合并后的新状态。根据全期望公式：

\[f(S) = 1 + p_{stay} \cdot f(S) + \sum_{i<j} p_{ij} \cdot f(S_{ij}) \]

解释：式子开头的 \(1\) 代表无论如何都消耗了这一步操作。

4. 移项整理（关键）
将 \(p_{stay} \cdot f(S)\) 移到等式左边：

\[f(S) - p_{stay} f(S) = 1 + \sum_{i<j} p_{ij} f(S_{ij}) \]

\[(1 - p_{stay}) f(S) = 1 + \sum_{i<j} p_{ij} f(S_{ij}) \]

因为 \(1 - p_{stay} = \sum_{i<j} p_{ij}\)（即选中有效块间点对的总概率），所以得到代码中的公式：

\[f(S) = \frac{1 + \sum_{i<j} p_{ij} \cdot f(S_{ij})}{\sum_{i<j} p_{ij}} \]

5. 边界
当 \(k=1\) 时，图已经连通，无需再走，\(f=0\)。记忆化搜索枚举所有 \(i<j\) 合并情况，状态数为整数划分数，\(n=35\) 时可行。