【习题选讲】概率与期望

概率与期望 
1
快乐期望 ~

期望题往往应用到了期望的线性性质，可以说是解题的基础。

在图上的解题方式一般就是：树上dp，基环树dp，DAG dp，缩点后 dp，分层图解同一层方程 dp

套路1. 直接递推/dp

$[NOI2005]-聪聪与可可$

简单题的样子，$f[i, j] = \frac{\sum f[nxt, k]}{deg_j + 1} + 1$，其中 nxt 是 i 两步能到达的，k 是 j 一步能到达的。猫和鼠的距离不断减少，所以状态不会形成环，记忆化搜索就好了。

$[SCOI2008]-奖励关$

n 这么小一定是状压啦。首先要明确的是，抛出什么宝物是随机的，但选择与否是我们决定的，也就是说我们要求最优策略下的最大期望得分

$f[i, S]$ 表示前 $i - 1$ 轮取到的状态为 $S$，$i$ ~ $K$ 轮的最大期望得分。那么就有

$[清华集训2017]-小 Y 和恐怖的奴隶主$

n 这么大一定是矩阵快速幂优化 dp 啦（雾）。以 $m = 3$ 为例，设 $f[i, a, b, c]$ 表示 $i$ 轮攻击后有 $a$ 个 1 血随从、$b$ 个 2 血随从、$c$ 个 3 血随从的概率，转移方程就很好想。。然后发现这个东西状态数是 166, 复杂度 $O(T166^3logn)$，考虑把 $2^i$ 的矩阵预处理出来，每次询问就只需用一个行向量去乘 logn 次矩阵，复杂度就变成了 $O(T166^2logn)$，然后还要卡很多常。。。所以这是道毒题

套路2. 无限循环转递推

（这部分好神仙的！要巧妙设计状态，或者错位相减法（等比数列求和必备技能）等方法化柿子 qvq）

$[SHOI2002]-百事世界杯之旅$

应用极限的思想 题解

$[六省联考2017]-分手是祝愿$

看起来很神的期望题

首先 50 分从后往前取，好拿吧

考虑正解！从后往前取会确定一些必须要取的键，那么就相当于除开这些键 按了其他的键 就得按同一个键按回来，相当于多了一个必须要按的键（所以 f 的预处理得从 n，不能从 cnt 开始！）。所以 dp 的状态就是 f[i] 表示从 i 个必选的键转移到 i - 1 个必选的键的期望操作次数

第一项表示选了一个必选的，一次就到 i - 1 去了；

第二项表示选了一个其他的，就得 f[i + 1] 次按回来，再 f[i] 次按到 i - 1 去。

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define int long long
using namespace std;

const int mod = 100003, N = 1e5 + 10;
typedef long long ll;
ll n, K, cnt, res;
ll col[N], f[N];

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

signed main() {
    cin >> n >> K;
    rep(i, 1, n) scanf("%d", &col[i]);
    for (int i = n; i; --i) {
        if (col[i]) {
            ++cnt;
            for (int j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    col[j] ^= 1;
                    if (j * j != i) col[i / j] ^= 1;
                }
            }
        }
    }
    for (int i = n; i; --i)  // !!! 从 n 开始
        f[i] = (f[i + 1] * (ll)(n - i) % mod + n) % mod * quick_pow(i, mod - 2) % mod;
    if (cnt <= K) res = cnt;
    else {
        res = K;
        for (int i = cnt; i > K; --i) res = (res + f[i]) % mod;
    }
    rep(i, 1, n) res = res * (ll)i % mod;
    printf("%lld\n", res);
    return 0;
}

$[UVA10529]-Dumb Bones$

太神仙了吧woc

考虑单独一张骨牌摆放成功的期望次数 E

玄学化柿子（感性理解）

（别化晕了

考虑连续的 x 张骨牌成功的期望。注意采取最优策略

放第 x 张骨牌时，如果向左/右，就要花费一些步数去扶起左/右边的骨牌。后面那坨东西，根据期望的线性性质

以往左倒为例解释一下：左边要重搭 $f[i - 1] \times [往左倒的期望次数] = f[i - 1] \times (E - 1) \times \frac{pl}{pl + pr}$，注意这是重搭的，初始还有一次，所以是 $f[i - 1] \times \frac{1 - pr}{1 - pl - pr}$

就做完了。uva 数据只有一组，非常的水，我怕了，题解柿子都不一样。

感想就是，期望的线性性质真的太重要了！ 不然这种互相影响的问题就没法做了。

$[CF908D]-New Year and Arbitrary Arrangement$

这题的关键在处理边界啦。

容易发现我们需要记录的是当前 a 和 ab 的数量。设 f[i, j] 表示 i 个 a，j 个 ab，那么 $f[i, j] = \frac{pa}{pa + pb}f[i + 1, j] + \frac{pb}{pa + pb}f[i, i + j]$

开头无限多个 b 怎么办？忽略掉，因为对 ab 的数量没有影响。

结尾无限多个 a 怎么办？这个就要搞一搞了。如果 i + j >= k，那么只要加一个 b 就能结束。设 $P_a = \frac{pa}{pa + pb}$, $P_b = \frac{pb}{pa + pb}$

$「PKUWC2018」猎人杀$

很妙的概率题。

分母是变化的，很不好求。

问题可以转化一波，变成：死掉的猎人依旧算在概率里面，每一轮一直开枪直到射死一个没死过的猎人。这样每次能选的就是全集了。

设 $W = \sum w_i$, $T = \{w_i | (i has died)\}$, $sum(T) = \sum\limits_{i has died} w_i$

转化前射死 $i$ 的概率 $P = \frac{wi}{(W - T)}$

转化后射死 $i$ 的概率 $P = \frac{T}{W}P + \frac{wi}{W} = \frac{wi}{W - T}$

两者相等。

。

。

然后考虑容斥，钦定一个不包含 1 的猎人集合 T 在 1 之后死去。除了集合 T 和猎人 1 以外的剩余的猎人不用考虑，因为他们可以任意摆放在 1 的前面后面（也就是说概率是 1）

集合为 T 的人在 1 后面死的概率：

容斥

枚举 $T$ 再背包预处理容斥系数可以做到 $n^2$，50 pts：

好妙【吐血而亡

100 pts 的话就是后面那坨容斥系数用分治的 NTT 卷一下了（下标是 T），注意不是 cdq 分治，就是普通的分治。或者也可以堆优化，即每次选两个长度最小的卷。nlog^2n

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 998244353, N = 3e5 + 10, G1 = 3, G2 = (mod + 1) / G1;
typedef long long ll;
ll n, w[N], lim, sum[N], stk[32], top, g[32][N], ans, f[N], L, rev[N];

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

void get_rev() {
    rep(i, 1, lim - 1)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}

void NTT(ll a[], int op) {
    rep(i, 1, lim - 1)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
        ll W = quick_pow(op == 1 ? G1 : G2, (mod - 1) / (mid << 1));
        for (int j = 0; j < lim; j += (mid << 1)) {
            ll w = 1;
            for (int k = 0; k < mid; k++, w = w * W % mod) {
                ll x = a[j + k], y = w * a[j + k + mid] % mod;
                a[j + k] = (x + y) % mod, a[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (op == -1) {
        ll Inv = quick_pow(lim, mod - 2);
        rep(i, 0, lim - 1) a[i] = a[i] * Inv % mod;
    }
}

void solve(ll f[], int l, int r) {
    if (l == r) {
        f[0] = 1, f[w[l]] = mod - 1; return;
    }
    int mid = (l + r) >> 1, ls, rs;
    ls = stk[top--], solve(g[ls], l, mid);
    rs = stk[top--], solve(g[rs], mid + 1, r);
    lim = 1, L = 0;
    while (lim <= sum[r] - sum[l - 1]) lim <<= 1, ++L;
    get_rev();
    NTT(g[ls], 1), NTT(g[rs], 1);
    rep(i, 0, lim - 1) f[i] = g[ls][i] * g[rs][i] % mod;
    NTT(f, -1);
    rep(i, 0, lim - 1) g[ls][i] = g[rs][i] = 0;
    stk[++top] = ls, stk[++top] = rs;  // 垃圾回收
}

int main() {
    cin >> n;
    rep(i, 1, n) scanf("%lld", &w[i]), sum[i] = sum[i - 1] + w[i];
    rep(i, 1, 30) stk[++top] = i;
    solve(f, 2, n);
    rep(i, 0, sum[n] - w[1])
        ans = (ans + w[1] * quick_pow(i + w[1], mod - 2) % mod * f[i] % mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

套路3. 高斯消元

终于到了我最喜欢的部分 ~ 高消！

我纠结了很久的问题：图上游走问题 是以出发点度数作为分母还是终点度数作为分母，但这其实应题而异，主要跟你设计的 dp 状态有关。

$[USACO10HOL]-Driving Out the Piggies G$

$f[x]$ 表示走到 x 不爆炸的概率（爆炸只要乘上 $\frac{p}{q}$ 就好了）

对于非起始点的 x，$f[x] = \sum \frac{(1 - \frac{p}{q})f[y]}{deg_y}$

$[HNOI2013]-游走$

几个月前做的，现在来看却有了新的体会。

根据期望的线性性质，$E[分数之和] = \sum_{(u, v) \in G} E[(u, v)分数] = \sum_{(u, v) \in G} E[经过(u, v)的次数] \times val(u, v)$，那么算出每条边被经过次数后从小到大排序，贪心的从大到小赋边权就可以了。

边经过的期望次数可以转化成点经过的期望次数。$E[u, v] = \frac{E[u]}{deg_u} + \frac{E[v]}{deg_v}$, $E[u] = \sum \frac{E[v]}{deg_v} + [u == 1]$

$[HNOI2011]-XOR和路径$

整个做不好做。根据期望的线性性质，按位考虑，计算出每一位为 1 的概率直接相加。$f[x]$ 表示从 x 到 n 当前位为 1 的概率。

移项以后高消。注意边界，$f[n] = 0$

套路4. 分开考虑贡献

这部分主要是期望的线性性质的应用。其实前面的题目也有体现。

$仓鼠找sugar II$

数据范围这么大 不能高消 => 我不会做了！

把目标节点看作根，这样答案就成了到达根的期望步数和

设 $f[x]$ 表示从 x 向上走一步的期望步数，那么 $f[x] = \frac{1}{deg_x} + \frac{deg_x - 1}{deg_x}(1 + \frac{\sum\limits_{y \in Son(x)} f[y]}{deg_x - 1} + f[x]) = 1 + \frac{\sum\limits_{y \in Son(x)} f[y]}{deg_x} + f[x] = deg_x + \sum\limits_{y \in Son(x)}f[y]$, 叶子 $x$ 的 $f[x] = 1$

树形dp $n$ 次能获得 50 分的好成绩，考虑再优化——换根法。

设 $g[x]$ 表示在 $fa[x]$ 的儿子中除了 $x$ 以外的 $f$ 值之和。根从 $u$ 变成 $v$ 实际上只会影响 $u$ 和 $v$ 的 $f$ 值和子树大小，即 $f[u] = deg_u + g[v], f[v] = 0$，子树和随便搞一下。$ans = \frac{\sum\limits_{rt = 1}^n\sum\limits_{x = 1}^n f[x] \times sz[x]}{n^2}$

$小魔女帕琪$

根据期望的线性性质，$E[总数] = \sum\limits_i E[从 i 开始的七个魔法都不相同]$，每个位置 i 的连续七个不相同的概率都是相同的。答案就是 $7! \times \prod\limits_{i = 1}^7 \frac{a_i}{N - i + 1} \times (N - 6)$

$[HNOI2015]-亚瑟王$

根据期望的线性性质，考虑每张牌对答案的贡献。发现第 $i$ 张牌被考虑到的次数只和前 $i - 1$ 张牌产生贡献的数量有关（设其为 $j$），因为这 $j$ 张牌产生贡献的时间和顺序不论怎样变换，第 $i$ 张牌都能被考虑到 $r - j$ 次。

于是想到 dp。$f[i, j]$ 表示在 $r$ 轮中前 $i$ 张牌有 $j$ 张产生贡献的概率，$g[i]$ 表示第 $i$ 张牌产生贡献的概率。那么

最终 $ans = \sum\limits_{i = 1}^n g[i] \times d[i]$

最终答案就是 $f[1, 0]$

套路5. 整数概率公式

这部分是真的没怎么练过。。

反正要知道公式：对于随机变量 $k >= 0$, $E(k) = \sum\limits_{i = 0}^{\infty} P(k \ge i)$

$随机数生成器$

根据上面那个公式，我们就是要计算出 $P(ans \ge i)$。发现 $\ge$ 不好求，$\leq$ 挺好求，因为每个区间里至少有一个 $\leq i$ 的就算满足条件了，所以考虑将 $P(ans \ge i)$ 转化为 $1 - P(ans < i)$。

我们发现两个区间是包含关系的话，大的区间对答案没有贡献，于是操作一波使得区间们的左右端点不减。考虑某个位置的数，如果它 $\leq i - 1$ 就能对覆盖自己的区间产生贡献，而且覆盖自己的区间编号连续。考虑将点和区间互换，问题等价于每个点能覆盖一些区间，且覆盖的概率为 $p = \frac{i - 1}{x}$，用一些点去覆盖所有区间的概率。

容易想到 dp，设 $l[i]$ 表示点 i 覆盖的最左边的区间，$r[i]$ 是最右边的，$f[i]$ 表示强制选第 i 个点，然后覆盖了 $1$ ~ $r[i]$ 所有区间的概率，那么

最终答案就是 $\sum\limits_{r[i] = Q}f[i] \times (1 - p)^{n - i}$

直接做是 $n^3$ 的，前缀和维护一下就好了。

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 2e3 + 10, mod = 666623333;
int n, x, Q, top, L, R;
int stk[N], l[N], r[N];
ll f[N], ans, pre[N];
struct node { int l, r; }q[N];

bool cmp(node a, node b) {
    return a.l == b.l ? a.r > b.r : a.l < b.l;
}

ll qpow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

void prework() {
    sort(q + 1, q + Q + 1, cmp);
    rep(i, 1, Q) {
        while (top && q[stk[top]].r >= q[i].r) --top;
        stk[++top] = i;
    }
    Q = top;
    rep(i, 1, Q) q[i] = q[stk[i]];
    L = 1, R = 0;
    rep(i, 1, n) {
        while (R < Q && q[R + 1].l <= i) ++R;
        while (L <= R && q[L].r < i) ++L;
        l[i] = L, r[i] = R;
    }
}

int main() {
    cin >> n >> x >> Q;
    rep(i, 1, Q) scanf("%d%d", &q[i].l, &q[i].r);
    prework();
    rep(i, 1, x) {
        ll sum = 0, tot = 1;
        ll p = (i - 1) * qpow(x, mod - 2) % mod;
        ll pp = mod + 1 - p;
        ll invp = qpow(pp, mod - 2);
        int lst = 0;
        memset(f, 0, sizeof(f));
        f[0] = 1;
        rep(j, 1, n) {
            while (lst < j && r[lst] < l[j] - 1)
                tot = (tot - f[lst] * qpow(invp, lst) % mod + mod) % mod, ++lst;
            f[j] = p * tot % mod * qpow(pp, j - 1) % mod;
            tot = (tot + f[j] * qpow(invp, j) % mod) % mod;
        }
        for (int j = n; j && r[j] == Q; --j) sum = (sum + f[j] * qpow(pp, n - j) % mod) % mod;
        ans = (ans + 1 - sum + mod) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}