奖池还会继续累加

P1654 OSU!

考虑记录 $a_i$ 位前 $i$ 位且第 $i$ 位为 $1$ 的连续 $1$ 长度的期望，注意这里对于诸如 $1101$ 的贡献为 $1$。

那么有 $a_i = (a_{i - 1} + 1) \times p_i$。

同样我们记录 $b_i$ 表示平方，$c_i$ 表示立方。

那么有 $b_i = (b_{i - 1} + 2\times a_{i - 1} + 1) \times p_i$, $c_i = ({c_{i - 1} + 3 * b_{i - 1} + 3 * a_{i - 1} + 1}) \times p_i$。

但会发现此时的 $c_i$ 不能作为答案，我们把 $c_i$ 的递推式改为 $c_i = ({c_{i - 1} + 3 * b_{i - 1} + 3 * a_{i - 1} + 1}) \times p_i + c_{i - 1} \times (1 - p_i)$ 就变成总和了。

P4316 绿豆蛙的归宿

期望公式：$E(ax + by) = aE(X) + bE(y)$

令 $f[u]$ 表示 $u$ 到 $n$ 的期望长度。

则 $f[u] = \frac{1}{k}\sum_{v\in son(u)}(w[u][v] + f[v])$，其中 $w[u][v]$ 指 $u$ 到 $v$ 的距离

初值 $f[n] = 0$，可拓扑，也可记忆化。

UVA12369 Cards

$f[a][b][c][d][x][y]$：$a$ 张 $1$，$b$ 张 $2$，$c$ 张 $3$，$d$ 张 $4$，小王代表第 $x$ 种花色，大王代表第 $y$ 种花色。（$x = 0$ 代表还没有使用）

转移：$f[a][b][c][d][x][y] <- \left\{\begin{matrix} \\ \frac{13 - a}{54 - sum}(f[a + 1][b][c][d][x][y] + 1) \ \ \ \ \ a < 13 \\ \frac{13 - b}{54 - sum}(f[a][b + 1][c][d][x][y] + 1) \ \ \ \ \ b < 13 \\ \frac{13 - c}{54 - sum}(f[a][b][c + 1][d][x][y] + 1) \ \ \ \ \ c < 13 \\ \frac{13 - d}{54 - sum}(f[a][b][c][d + 1][x][y] + 1) \ \ \ \ \ d < 13 \\ \underset{i\in\{0, 3\}}\min(f[a][b][c][d][i][y]) + 1 \ \ \ \ \ x = 4 \\ \underset{i\in\{0, 3\}}\min(f[a][b][c][d][x][i]) + 1 \ \ \ \ \ y = 4 \end{matrix}\right.$

记得记忆化。

double dp(int a, int b, int c, int d, int x, int y) {
    if (a > 13 || b > 13 || c > 13 || d > 13) return INF;
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    int sum = a + b + c + d + (x != 4) + (y != 4);
    int sa = a + (x == 0) + (y == 0), sb = b + (x == 1) + (y == 1);
    int sc = c + (x == 2) + (y == 2), sd = d + (x == 3) + (y == 3);
    int rest = 54 - sum;
    if (sa >= A && sb >= B && sc >= C && sd >= D) return v = 0;
    if (rest <= 0) return v = INF;
    v = 1;
    if (a < 13) v += (13.0 - a) / rest * dp(a + 1, b, c, d, x, y);
    if (b < 13) v += (13.0 - b) / rest * dp(a, b + 1, c, d, x, y);
    if (c < 13) v += (13.0 - c) / rest * dp(a, b, c + 1, d, x, y);
    if (d < 13) v += (13.0 - d) / rest * dp(a, b, c, d + 1, x, y);
    if (x == 4) {
        double t = INF;
        for (int i = 0; i < 4; i ++) t = min(t, 1.0 / rest * dp(a, b, c, d, i, y));
        v += t;
    }
    if (y == 4) {
        double t = INF;
        for (int i = 0; i < 4; i ++) t = min(t, 1.0 / rest * dp(a, b, c, d, x, i));
        v += t;
    }
    return v;
}

CF24D

$f[i][j]$ : 从 $(i, j)$ 走到第 $n$ 行的期望步数

转移：

1. $j = 1$ 时，$f[i][j] = \frac{1}{3}(f[i][j] + f[i][j + 1] + f[i + 1][j])$
2. $j = 2 \sim m - 1$ 时，$f[i][j] = \frac{1}{4}(f[i][j - 1] + f[i][j] + f[i][j + 1] + f[i + 1][j])$
3. $j == m$ 时，$f[i][j] = \frac{1}{3}(f[i][j - 1] + f[i][j] + f[i + 1][j])$

悲伤的是这个方程显然有后效性，但我们可以移项一下进行高斯消元。

我们发现系数矩阵是这个样子的。

$\begin{bmatrix} & x & x & 0 & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ & x & x & x & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ &…& \\ & 0 & 0 & … & 0 & x & x & x & \ \ \ \ \ \ x & \\ & 0 & 0 & … & 0 & 0 & x & x & \ \ \ \ \ \ x & \end{bmatrix}$

先消成

$\begin{bmatrix} & x & x & 0 & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ & 0 & x & x & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ &…& \\ & 0 & 0 & … & 0 & 0 & x & x & \ \ \ \ \ \ x & \\ & 0 & 0 & … & 0 & 0 & 0 & x & \ \ \ \ \ \ x & \end{bmatrix}$

再消成

$\begin{bmatrix} & x & 0 & 0 & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ & 0 & x & 0 & 0 & 0 & … & 0 & \ \ \ \ \ \ x & \\ &…& \\ & 0 & 0 & … & 0 & 0 & x & 0 & \ \ \ \ \ \ x & \\ & 0 & 0 & … & 0 & 0 & 0 & x & \ \ \ \ \ \ x & \end{bmatrix}$

就做完了。这样高斯消元复杂度是 $O(m)$，然后每行消一次即可。

注意当 $m = 1$ 时直接输出 $2(n - x)$。

Submission #302701523 - Codeforces