跳转至

Expectation

基本的一些东西可以看这里

期望 dpψ(｀∇´)ψ

期望 dp 和概率 dp 的区别就在于，期望 dp 还需要考虑取值问题。

所以一般情况下，期望 dp 的处理都比概率 dp 稍要复杂一些，不过其实也不算太难。

ABC280E Critical Hitψ(｀∇´)ψ

有一个 \(n\) 滴血的怪物。每一次攻击你有 \(P\%\) 的概率让它失去 \(2\) 滴血，有 \((100-P)\%\) 的概率让它失去 \(1\) 滴血。

如果攻击过后怪物的血量 \(\leq 0\)，它就死了。你需要一直攻击怪物直到它死亡。输出攻击次数的期望对 \(998244353\) 取模的值。

\(1\leq n\leq 2\times10^5,0\leq P\leq 100\)。

设 \(dp(i)\) 表示打死一只血量为 \(i\) 的怪物的步数期望。

因为血量为 \(1\) 的时候怎么打都是 gg，所以 \(dp(1) = 1\)。

方程比较显然，如果当前打掉了 \(1\) 滴血，那么应当从 \(dp(i - 1)\) 转移过来，概率为 \(\dfrac{100 - P}{100}\)，攻击次数加一。

否则从 \(dp(i - 2)\) 转移过来，概率为 \(\dfrac{P}{100}\)。

可以得到方程：

\[dp(i) = \dfrac{100 - P}{100}dp(i - 1) + \dfrac{P}{100}dp(i - 2) + 1\]

我们这里省去了直接代入期望的定义的过程，只需要乘法分配律一下就可以知道式子的正确性了。

你可以把上一个状态看作这个状态的一个取值，不过其本质还是推式子。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
// using i64 = long long;
#define int long long

const int si = 2e5 + 10;
const int mod = 998244353;

int n, p;
int dp[si];
int qpow(int a, int b) {
    int ret = 1 % mod;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret % mod;
}
int inv(int x) { return qpow(x, mod - 2); }
const int iv = inv(100);

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> p;
    dp[0] = 0, dp[1] = 1; 
    for(int i = 2; i <= n + 1; ++i)
        dp[i] = ((dp[i - 1] * (100 - p + mod) % mod * iv % mod)
                + (dp[i - 2] * p % mod * iv % mod) + 1 % mod + mod) % mod;
    cout << dp[n] << endl;
    return 0;
}

Acwing217. 绿豆蛙的归宿ψ(｀∇´)ψ

给出一个有向无环的连通图，起点为 \(1\)，终点为 \(N\)，每条边都有一个长度。

数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有 \(K\) 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 \(\dfrac{1}{K}\)。

现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

\(1\le n \le 1e5, 1\le m \le 2e5\)。

首先我们注意到要求的是从 \(1 \to n\) 的路径长度的期望，也就是所有可能的路径长度乘上对应的概率。

显然我们不可能直接一个式子就把这个东西写出来，所以我们考虑期望递推/dp。

设 \(dp(u)\) 表示从 \(1 \to u\) 的路径长度的期望。

我们根据定义尝试推一下式子，假设 \(u\) 是从 \(v_1 \dots v_r\) 这些节点可以到达的。

假设 \(x(v_i)_j\) 表示从 \(1 \to v_i\) 的路径的某一种可能长度，\(p(v_i)_j\) 表示出现 \(x(v_i)_j\) 这种情况的概率。

那么就有：

\[ \begin{aligned} dp(u) &= \sum\limits_i\sum\limits_j(p(v_i)_j \times \dfrac{1}{deg(v_i)} \times (x(v_i)_j + w(u, v_i))) \\ &= \sum\limits_i(\dfrac{1}{deg(v_i)} \times \sum\limits_j (p(v_i)_j \times x(v_i)_j + p(v_i)_j \times w(u, v_i))) \\ &= \sum\limits_i(\dfrac{1}{deg(v_i)} \times (dp(v_i) + w(u, v_i) \times \sum\limits_j p(v_i)_j)) \end{aligned} \]

注意到 \(\sum\limits_j (p(v_i)_j)\) 就是从 \(1\) 出发，走到 \(v_i\) 的概率。

所以我们转移 dp 的时候顺带着处理一个数组 \(P(v_i)\) 表示从 \(1 \to v_i\) 的概率就行了。

初始化 \(dp(1) = 0\)，终态 \(dp(n)\)。

其实这种“正推”的方法比较麻烦，其原因在在于需要处理 \(P\) 这个数组，因为从 \(1 \to v_i\) 的概率是不能直接确定的。

注意到我们最后一定会走到 \(n\)，也就是说从 \(\forall u \not= n, P(u \to n) = 1\)，那么如果我们考虑倒推会怎样呢？

设 \(dp(u)\) 表示从 \(u \to n\) 的路径长度期望，并且 \(u\) 可以到达 \(v_1 \dots v_r\)。

根据定义，类似正推，我们可以写出：

\[ \begin{aligned} dp(u) = \dfrac{1}{deg(u)}\sum\limits_i(dp(v_i) + w(u, v_i) \times \sum\limits_j p(v_i)_j) \end{aligned} \]

是不是基本一样？并不，注意到这里的 \(\sum\limits_jp(v_i)_j\) 表示的是从 \(v_i\) 出发走到 \(n\) 的概率，这个概率一定是 \(1\)，所以状态转移变为：

\[ \begin{aligned} dp(u) = \dfrac{1}{deg(v_i)} \sum\limits_i(dp(v_i) + w(u, v_i)) \end{aligned} \]

然后转移就不用额外维护信息了。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;

const int si = 1e5 + 10;

int n, m;
int tot = 0, head[si];
struct Edge { int ver, Next, w; } e[si << 1];
inline void add(int u, int v, int w) { e[tot] = (Edge) {v, head[u], w}, head[u] = tot++; }

std::queue<int> q;
int deg[si], k[si];
ldb dp[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(head, -1, sizeof head);
    cin >> n >> m, dp[n] = 0;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(v, u, w), deg[u]++, k[u]++;
    }
    q.push(n);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = e[i].Next) {
            int v = e[i].ver, w = e[i].w;
            deg[v] --;
            dp[v] += (dp[u] + 1.0 * w) / (1.0 * k[v]);
            if(!deg[v]) q.push(v);  
        }
    }
    cout << fixed << setprecision(2) << dp[1] << endl;

    return 0;
}

[HNOI2013] 游走ψ(｀∇´)ψ

小 Z 在该图上进行随机游走，初始时小 Z 在 \(1\) 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 \(n\) 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 \(m\) 条边进行编号，使得小 Z 获得的总分的期望值最小。

保证 \(2\leq n \leq 500\)， \(1 \leq m \leq 125000\)，\(1 \leq u, v \leq n\)，给出的图无重边和自环，且从 \(1\) 出发可以到达所有的节点。

先直接考虑算边的贡献，直接算的话，没法 \(O(m)\) 的，注意到 \(n \le 500\)，我们从 \(n\) 入手。

可以设 \(g(i)\) 表示编号为 \(i\) 的边被经过的期望次数，我们让 \(g(i)\) 大的编号小即可，这个是排序不等式。

如果 \(f(i)\) 表示点 \(i\) 被经过的次数，那么 \(g(u \to v) = \dfrac{f(u)}{d(u)} + \dfrac{f(v)}{d(v)}\)。

其中 \(d\) 表示度数，而 \(f(i) = \sum\limits_{v \to u\land v\not=n} \dfrac{f(v)}{d(v)},(i \not= 1)\)。

如果 \(i = 1, f(i) = \sum\limits_{v \to u \land v\not= n} \dfrac{f(v)}{d(v)} + 1\)。

然后这就是一个线性方程组，高斯消元即可，复杂度 \(O(n^3)\)。

Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;

const ldb eps = 1e-5;
const int si = 5e2 + 10;
const int sim = 5e5 + 10;

int n, m;
int tot = 0, head[si];
struct Edge { int ver, Next; } e[sim];
inline void add(int u, int v) { e[tot] = (Edge){v, head[u]}, head[u] = tot++; } 
int from[sim], to[sim];

ldb f[sim], deg[si];
namespace Gauss {
    ldb x[si];
    ldb c[si][si], d[si];
    void fill() {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                c[i][j] = 0.0;
            d[i] = 0.0, x[i] = 0.0;
        }
        for(int u = 1; u < n; ++u) {
            for(int i = head[u]; ~i; i = e[i].Next) {
                int v = e[i].ver;
                if(v == u) continue;
                c[u][v] = (1.0 / deg[v]);
            }
            c[u][u] = -1.0, d[u] = -0.0;
        }
        d[1] = -1.0, x[n] = 0.0;
    }
    void solve() {
        for(int i = 1; i < n; ++i) {
            int l = i;
            for(int j = i + 1; j < n; ++j)
                if(fabs(c[j][i]) - fabs(c[l][i]) > eps)
                    l = j;
            if(l != i) {
                for(int j = 1; j <= n; ++j)
                    swap(c[l][j], c[i][j]);
                swap(d[l], d[i]);
            }
            if(fabs(c[i][i]) >= eps) {
                for(int j = 1; j < n; ++j) {
                    if(i == j) continue;
                    ldb rate = c[j][i] / c[i][i];
                    for(int k = 1; k <= n; ++k)
                        c[j][k] -= c[i][k] * rate;
                    d[j] -= rate * d[i];
                }
            }
        }       
        for(int i = n - 1; i >= 1; --i) {
            for(int j = i + 1; j < n; ++j)
                d[i] -= x[j] * c[i][j];
            x[i] = d[i] / c[i][i];
        }
    }
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v; 
        add(u, v), add(v, u);
        from[i] = u, to[i] = v;
        deg[u] += 1.0, deg[v] += 1.0;
    }
    Gauss::fill(), Gauss::solve();
    for(int i = 1; i <= m; ++i) {
        if(from[i] != n) f[i] += Gauss::x[from[i]] / deg[from[i]];
        if(to[i] != n) f[i] += Gauss::x[to[i]] / deg[to[i]];
    }
    ldb ans = 0.0;
    sort(f + 1, f + 1 + m); 
    for(int i = 1; i <= m; ++i)
        ans += f[i] * (m - i + 1);

    cout << fixed << setprecision(3) << ans << endl;

    return 0;
}

CF24D Broken Robotψ(｀∇´)ψ

\(n\) 行 \(m\) 列的矩阵，现在在 \((x,y)\)，每次等概率向左，右，下走或原地不动，但不能走出去，问走到最后一行期望的步数。

注意，\((1,1)\) 是木板的左上角，\((n,m)\) 是木板的右下角。

\(1\le n,m\le 10^3\)，\(1\le x\le n\)，\(1\le y\le m\)。

方程是比较显然的，如果设 \(dp(x, y)\) 表示从 \(x, y\) 走到最后一行的期望。

然后考虑边界分开转移，方程略，可以写成高斯消元的形式，注意到系数矩阵比较特殊：

\[ \begin{bmatrix} &-\frac{2}{3} &\frac{1}{3} &0 &0 \\ &\frac{1}{4} &-\frac{3}{4} &\frac{1}{4} &0 \\ &0 &\frac{1}{4} &-\frac{3}{4} &\frac{1}{4} \\ &0 &0 &\frac{1}{3} &-\frac{2}{3} \end{bmatrix} \]

直接从下往上回代就是 \(O(n^2)\) 的了，类似的还有：分手是祝愿。

这个东西很好玩的。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;
using ldb = long double;

const int si = 1e3 + 10;

ldb dp[si][si];
int n, m, x, y;
namespace Gauss {
    ldb c[si][si];
    void solve() {
        for(int j = n - 1; j >= 1; --j) {
            for(int i = 1; i <= m; ++i) {
                c[i][i] = 3, c[i][i - 1] = c[i][i + 1] = -1;
                c[i][m + 1] = 4 + dp[j + 1][i];
                if(i == 1) c[i][m + 1]--, c[i][i]--;
                if(i == m) c[i][m + 1]--, c[i][i]--;
            }
            for(int i = 1; i <= m; ++i) {
                if(c[i][i] == 0) {
                    cout << "No Solution" << endl;
                    exit(0);
                }
                else {
                    if(i != m)
                        c[i][i + 1] = c[i][i + 1] / c[i][i];
                    c[i][m + 1] = c[i][m + 1] / c[i][i], c[i][i] = 1;
                    if(i != m) {
                        c[i + 1][i + 1] = c[i + 1][i + 1] - c[i + 1][i] * c[i][i + 1];
                        c[i + 1][m + 1] = c[i + 1][m + 1] - c[i + 1][i] * c[i][m + 1];
                        c[i + 1][i] = 0;
                    }
                }
            }
            for(int i = m; i >= 1; --i) {
                dp[j][i] = c[i][m + 1];
                if(i != 1) c[i - 1][m + 1] -= c[i - 1][i] * dp[j][i];
            }
        }
    }
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m >> x >> y;
    for(int i = 1; i <= m; ++i) dp[n][i] = 0.0;
    Gauss::solve(), cout << fixed << setprecision(10) << dp[x][y];

    return 0;
}

总结ψ(｀∇´)ψ

求解期望 DP 时，可以将上一个状态当作下一个状态的随机变量的取值，进而简化转移。

其本质类似：\(\sum (x_ip_i\times P) = P \times \sum(x_ip_i)\)。

很多时候，正推需要额外处理概率，在确定终态的情况下，我们可以考虑倒推，借此来省去处理概率的繁琐步骤。

如果方程有后效性的话，那么还需要套上一个高斯消元。

最后更新: May 9, 2023