「专题选做」概率与期望题目选做 1

TorusSailing

「Topcoder 12984」TorusSailing

题目描述

有 $n \times m$ 的网格，一人从 $(1, 1)$ 随机游走，每次等概率向下或向右，问走到 $(x, y)$ 的期望步数。

数据范围：$n, m \le 100$。

思路分析

$f(i, j)$ 表示 $(i, j)$ 走左、上游走到 $(1, 1)$ 的期望时间。发现所有两维坐标都 $\ge 2$ 的 $f(a, b)$ 都可以用 $f(1, i)$ 和 $f(i, 1)$ 的线性组合表出，于是我们列出关于 $f(1, i)$ 和 $f(i, 1)$ 的方程并用高斯消元解出即可，时间复杂度 $O(n^3)$。

代码实现

#include <bits/stdc++.h>

Maze

「HDU 4035」Maze

题目描述

给定一棵 $n$ 个点的树，一个人在 $1$，每次有 $k_i$ 的概率传送回 $1$，有 $e_i$ 的概率逃出，有 $1 - k_i - e_i$ 的概率随机游走到邻居。问逃出时走过边数的期望。

数据范围：$T \le 30, n \le 10^4$。

思路分析

$f(u)$ 表示从 $u$ 出发经过边数的期望。记 $p_u$ 表示 $u$ 的父亲，$d_u$ 表示 $u$ 的度数，那么有：

$$f(u) = k_uf(1) + \frac{1 - k_u - e_u}{d_u}\sum_{(u, v) \in E}f(v) + 1$$

更具体地，对于非根结点 $v$，有：

$$f(v) = k_vf(1) + \left(\frac{1 - k_v - e_v}{d_v}\sum_{t \in \text{son}_v}f(t)\right) + \left(\frac{1 - k_v - e_v}{d_v}f(p_v)\right) + (1 - k_v - e_v)$$

对于根结点 $1$，有：

$$f(1) = k_1f(1) + \left(\frac{1 - k_1 - e_1}{d_1}\sum_{v \in \text{son}_1}f(v)\right) + (1 - k_1 - e_1)$$

可以把每个点表示成一个三元组 $(a_i, b_i, c_i)$ 表示 $f(i) = a_if(1) + b_if(p_i) + c_i$，然后在树上自底向上消元。注意对根结点要特判，时间复杂度 $O(n)$。

代码实现

#include <bits/stdc++.h>

分手是祝愿

「LOJ 2145」分手是祝愿

题目描述

有 $n$ 个灯泡，给定它们的明暗状态。还有 $n$ 个开关，第 $i$ 个按下后就把编号为它的所有因数的灯泡取反，一个人随机操作开关，直到有一种方案操作 $\le k$ 次把所有灯变暗时采用最优策略，问期望操作次数。

数据范围：$n \le 10^5$。

思路分析

根据灯泡的明暗序列我们可以直接推出最优的操作序列，于是问题就变成给定 01 串，每次选一个位置取反，直到有 $\le k$ 个 1 时停止。记 $f_i$ 表示从 $i$ 个 1 变成 $i - 1$ 个 1 的期望步数，那么有：

$$\begin {align*} f_i & = \frac{(n - i)\left(f_{i + 1} + f_i\right)}{n} + 1 \\ \frac{i \cdot f_i}{n} & = \frac{(n - i)f_{i + 1}}{n} + 1 \\ f_i & = \frac{(n - i)f_{i + 1} + n}{i} \end {align*}$$

干就完了，时间复杂度 $O(n \sqrt n)$。

代码实现

#include <bits/stdc++.h>

歌唱王国

「Luogu 4548」歌唱王国

题目描述

给定长度为 $n$ 的串，有空串 $S$，每次在 $S$ 末尾加入一个 $[1, m]$ 的字符，直到 $S$ 的后缀为给定串时停止。问 $S$ 的期望长度。

数据范围：$T \le 50, n, m \le 10^5$。

思路分析

记 $f(i)$ 表示 $\vert S \vert$ 为 $i$ 的概率，那么 $i < n$ 时 $f(i) = 0$，$i \ge n$ 时有转移方程：

$$f(i) = \displaystyle{\frac{1}{m^n} - \sum_{j = 1}^{n - 1} [s(1, j) = s(n - j + 1, n)] \frac{f(i + j - n)}{m^{n - j}} - \frac{1}{m^n} \sum_{j = 0}^{i - n} f(j)}$$

令 $a_i = [s(1, i) = s(n - i + 1, n)], g(i) = \sum_{j = i + 1}^{\infty} f(j)$，那么有 $g(0) = \sum_{i = 1}^{\infty} f(i) = 1$。我们把它代入 $f$ 的转移方程得到：

$$f(i) = \frac{1}{m^n} - \sum_{j = 1}^{n - 1} a_j \frac{f(i + j - n)}{m^{n - j}} - \frac{1}{m^n} \left(g(0) - g(i - n)\right) \\ \frac{1}{m^n} g(i) = \sum_{j = 1}^{n} a_j \frac{f(i + j)}{m^{n - j}} \\$$

我们要求的是 $\sum_{i = 1}^{\infty} f(i) \cdot i$，也就是 $\sum_{i = 0}^{\infty} g(i)$。把 $f, g$ 的生成函数记为 $F, G$，那么我们求的就是 $G(1)$。将转移方程改写，得：

$$G(x) \left(\frac{x}{m}\right)^n = \sum_{j = 1}^{n} a_j F(x) \left(\frac{x}{m}\right)^{n - j} \\ G(1) \left(\frac{1}{m}\right)^n = \sum_{j = 1}^{n} a_j F(1) \left(\frac{1}{m}\right)^{n - j} \\ G(1) = \sum_{j = 1}^{n} a_j m^j \\$$

用 KMP 求出 $a_i$，直接计算，时间复杂度 $O(n)$。

#include <bits/stdc++.h>

硬币游戏

「Luogu 3706」硬币游戏

题目描述

有 $n$ 个人，每个人有一个长度为 $m$ 的 01 串。在初始为空的串 $S$ 末尾随机加入 0 或 1，直到 $S$ 的后缀是某个 01 串为止，持有该串的人胜利。问最终每个人胜利的概率。

数据范围：$n, m \le 300$。

思路分析

01 串可以分为三类：未终止态，终止态，非法态。记 $P_0$ 表示所有未终止态的概率和，$P_i$ 表示 $i$ 胜利的概率。拿样例举例，$n = m = 3$，三个串为 THT, TTH, HTT，我们考虑 $P_2$。首先随便选一个串后面加上 TTH，概率是 $0.125P_0$。发现有可能提前变成终止态，如果在加第一个字符时变成终止态，原串的一定是 TH，HT 结尾的，所以概率是 $0.25P_1 + 0.25P_3$。同理，如果在加第二个字符时变成终止态，概率是 $0.5P_3$。所以有 $P_2 = 0.125P_0 - 0.25P_1 - 0.75P_3$。类似地可以列出 $n$ 个方程，最后再外加一个 $\sum_{i = 1}^{n} P_i = 1$，用高斯消元解方程即可。时间复杂度 $O(n^3)$。

代码实现

#include <bits/stdc++.h>