2020-09-13发表2021-01-22更新OI笔记19 分钟读完 (大约2816个字)

概率期望学习笔记

众所周知，一个随机变量 $x$ 的数学期望定义为 $E(x)$，即是 $E(x)traodinary$ 的缩写形式，代表 $x$ 是一个非凡的数字……

概念

随机变量 $x$ 的数学期望 $E(x)$ 定义为 $x$ 的每种取值的概率加权和，可以理解为 $x$ 在平均情况下的取值，我们一般称其为「期望取值」。
举个例子，若 $x$ 有 $1/3$ 的概率为 $1$，有 $2/3$ 的概率为 $2$，则 $E(x)=1/3+2\times (2/3)=5/3$。

线性性

根据乘法结合律以及分配律，可以发现期望具有线性性，可以将其理解为「元素和的期望等于元素期望的和」，亦即：
$$ E(\Sigma x_i)=\sum E(x_i) $$ 设 $c$ 为常量，也容易验证：
$$E(x+c)=E(x)+c$$

一道简单题

有一个长度为 $n$ 的数列，一开始所有位置都未被访问。每次随机一个未被访问过的位置，将它和它之前的位置都标记为访问过，问期望操作次数。
$n\le 10^{18}$

考虑期望的线性性，答案就等于每个位置能被访问到的概率。一个位置 $i$ 能被访问到当且仅当它在所有它后面的数之前被访问，这个概率是 $\frac{1}{n-i+1}$，因此容易发现答案是调和级数 $H_n$，使用近似公式计算即可。

又一道简单题

有一个 $n$ 个节点的有根树，一开始所有节点都未被访问。每次随机一个未被访问过的节点，将它到根的路径上所有点都标记为访问过，问期望操作次数，对 $998244353$ 取模。
$n\le 10^7$

仿照上题，容易发现答案是 $\sum\limits_{i=1}^n\frac{1}{sz[i]}$，其中 $sz[i]$ 表示子树 $i$ 的大小，线性求逆即可。

双一道简单题

$n$ 堆石子，每堆有 $a_i$ 个，每次随机选一个石子，并取光它所在的那堆石子。问第一堆石子被取到的时间的期望。
$n\le 10^5$

根据期望的线性性，答案等于每堆石子在 $1$ 之前取到的期望之和，即 $1+\sum\limits_{i=2}^n\frac{a_i}{a_1+a_i}$，线性计算即可。

叒一道简单题

一个 $n$ 面的骰子，问每一面都被掷到的期望投掷次数。
$n\le 10^{18}$

此类问题被称作「赠券收集问题」。
设 $f[n]$ 为 $n$ 面掷出后还需投掷的次数的期望，易得 $f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$，整理得 $f[i]=f[i+1]+\frac{n}{n-i}$，从而有 $f[0]=nH_n$，利用公式计算即可。

叕一道简单题

求所有 $n!$ 个 $n$ 的全排列中，逆序对数的期望，对 $998244353$ 取模。
$n\le 10^{7}$

众所周知，$n$ 的全排列一共有 $\dfrac{n!}{2}\dbinom{n}{2}$ 个逆序对，即对每个二元组 $(i,j)$ 讨论一下它们是否会形成逆序对。
因此答案为 $\dfrac{\dfrac{n!}{2}\dbinom{n}{2}}{n!}=\dfrac{n(n-1)}{4}$。

一道栗题

一个长度为 $n$ 的 01 串按以下方式生成：第 $i$ 个位置有 $a_i$ 的概率为 1，$1-a_i$ 的概率为 0。01 串的价值如下计算：每一个极长全 1 子串的长度的三次方之和。
求该 01 串的价值的期望。
$n\le 10^5$

设 $l_1[i]$ 表示末尾一段极长全 1 子串长度的期望， $l_2[i]$ 表示末尾一段极长全 1 子串长度的平方的期望，设 $f[i]$ 为长度为 $i$ 的 01 串价值的期望，考虑到有 $(x+1)^3-x^3=3x^2+3x+1$，则有：
$$ f[i]=f[i-1]+a_i(3l_2[i-1]+3l_1[i-1]+1) $$ 即对最后加入的位置 $i$ 讨论了一下它对答案的贡献。同理有：
$$ \begin{aligned} l_1[i]&=a_i(l_1[i-1]+1) \newline l_2[i]&=a_i(l_2[i-1]+2l_1[i-1]+1) \end{aligned}$$ 于是可以做到 $O(n)$ 求出答案。
注意区分 $f[]$ 和 $l[]$ 的定义，前者是全局的期望价值，后者是末位极长全 1 串的期望价值，同时还需要区分一下 “长度的三次方的期望” 和 “长度的期望的三次方”。

又一道栗题

给定一颗 $n$ 个节点的有根树，$1$ 号节点为根，树上的每个节点 $u$ 都有一个权值 $c_u$。
你需要随机一个节点的排列 $P\in [n]$，并且按这个排列的顺序依次访问所有树上的节点。每当访问到树上的一个节点 $u$ 时，你需要将子树 $u$ 内所有节点的权值加上 $c_u$（包括点 $u$）。
问在一切的操作结束之后所有节点权值之和的期望。由于期望可能不是一个整数，请将它乘上 $n!$，并对 $10^9+7$ 取模。
$n\le 10^5$, 且保证树的形态随机

根据期望的线性性，我们只需要求出每个节点最后的期望权值即可。设这个东西是 $a_u$ ，容易发现 $a_u$ 的取值只与从根到 $u$ 的这一条祖孙链上的节点有关。
因为树的形态随机，所以树高是期望 $O(\sqrt{n})$ 的。设祖孙链长为 $d$，那么只需考虑 $O(d)$ 地求出 $a_u$ 即可。
运用贡献法考虑：期望权值 = $Σ$权值$×$期望累加次数，那么考虑预处理一个 $t[]$，使得 $a_u=\sum c_v·t_v$ 即可。

容易发现 $t_v$ 的取值只与 $u,v$ 的相对距离有关，则可以设 $f_i$ 表示考虑随机访问一个有 $n$ 位的序列 $a_1,a_2,…,a_n$，$a_1$ 在 $i$ 上的期望累加次数。
考虑一次累加应当是什么样子： $1\to p_1\to p_2\to …\to i$，且满足 $1<p_1<p_2<…<i$。这显然双射了一个上升子序列（IS）。
则 $f_i$ 即代表考虑所有 $P\in [i]$，$P$ 中以 $1$ 起始的 IS 的期望数量。这样我们可以直接拿组合数选出来，即有：
$$ f_i=\sum\limits_d \dbinom{i-1}{d-1}\dbinom{i}{d}(i-d)! $$ 于是就可以计算了，时间复杂度 $O(n\sqrt{n})$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e5 + 6;
const int P = 1e9 + 7;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

int n, a[CN], fac[CN], ifac[CN], f[CN];
int C(int n, int m) {return 1ll * (1ll * fac[n] * ifac[m] % P) * ifac[n - m] % P;}

int stk[CN], ans = 0;
void dfs(int u, int p, int dep){
	stk[dep] = a[u];
	for(int i = dep, j = 1; i; i--, j++) ans = (1ll * stk[i] * f[j] % P + ans) % P;
	for(int k = hd[u]; k; k = E[k].nxt){
		int v = E[k].to;
		if(v ^ p) dfs(v, u, dep + 1);
	}
}

int main()
{
    n = read();
	for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}
	for(int i = 1; i <= n; i++) a[i] = read();

    fac[0] = ifac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = qp(fac[n], P - 2);
	for(int i = n - 1; i; i--) ifac[i] = 1ll * (i + 1) * ifac[i + 1] % P;

    for(int i = 1; i <= 5000; i++){
		for(int d = 1; d <= i; d++){
			int prd = 1ll * C(i - 1, d - 1) * C(i, d) % P;
			prd = 1ll * prd * fac[i - d] % P, f[i] = (f[i] + prd) % P;
		}
		f[i] = 1ll * f[i] * ifac[i] % P;	 
	}

    for(int i = 1; i <= n; i++) ans = (ans + a[i]) % P;
	dfs(1, 0, 1), ans = 1ll * ans * fac[n] % P;
	
    printf("%d", ans);
}

双一道栗题

有 $n$ 种方法，每种方法需要 $k_i$ 条途径，第 $j$ 条途径有 $p[i,j]$ 的概率无法使用。每次可以查询任意一条途径可否使用，直到查询到一种能使用的方法，求最小的“最少查询次数的期望”。
$n,k_i \le 500$

容易发现对于任意一种方法，如果不将其全部查询完，那么这次查询是无意义的。对于任意一种方法，我们应当按照 $p[i,j]$ 降序排序的顺序去查询。
假定 $\forall i$，$p[i,j]$ 已经降序排序为 $p_1,p_2,…p_{k_i}$，那么考虑对所有方法进行排列，设 $E_i$ 为考虑 $[1:i]$ 中的方法时的答案，则有：
$$\begin{aligned} E_i&=p_1(1+E_{i-1}) + p_2(1-p_1)(2+E_{i-1})+…\newline &=k_iE_{i-1}+b_i \end{aligned} $$ 注意到还有 $\prod\limits_j (1-p_j)$ 的概率本次查询不会停止，把这部分加到常数项即可。
于是变成了一次函数嵌套的最小值问题，按 $(k_i-1)/b_i$ 升序排序即可，时间复杂度 $O(\sum k_i + n\log n)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define DB double
const int CN = 550;
const DB EPS = 1e-9;

int n, m, id[CN]; DB k[CN], b[CN], p[CN];
bool cmp(DB x, DB y) {return x > y;}
bool comp(int i, int j) {return k[i] * b[j] + b[i] < k[j] * b[i] + b[j];}

int main()
{
    n = read(); 
    for(int i = 1; i <= n; i++){
        m = read(); for(int j = 1; j <= m; j++) scanf("%lf", &p[j]);
        sort(p + 1, p + m + 1, cmp); DB prd = 1.0;
        if(p[1] > 1.0 - EPS) {i--, n--; continue;} while(m && p[m] <= EPS) m--;
        for(int j = 1; j <= m; j++) k[i] += p[j] * prd, b[i] += p[j] * prd * j, prd *= (1.0 - p[j]);
        b[i] += m * prd, id[i] = i;
    }

    sort(id + 1, id + n + 1, comp); DB ans = 0;
    for(int i, p = n; p; p--) i = id[p], ans = k[i] * ans + b[i];

    printf("%.9lf", ans);
}

叒一道栗题

有 $m$ 张牌，其中一张是王牌。现在你执行 $n$ 次如下操作：洗牌后查看第一张牌是什么。
令 $x$ 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 $m!$ 种牌的排列出现的概率均相等，求 $x^k$ 的期望值，对 $998244353$ 取模。
$n,m\le 998244352, k\le 5000$

题目等价于：有 $n$ 个相互独立的随机变量 $x_1,x_2,…x_n$，每个变量有 $\frac{1}{m}$ 的概率为 $1$，其余情况为 $0$，求：
$$E[\left(\sum\limits_{i=1}^nx_i\right)^k]$$

根据期望的线性性，可以枚举 $d=\sum\limits_{i=1}^nx_i$，则有：
$$\begin{aligned} E[\left(\sum\limits_{i=1}^nx_i\right)^k] &=\sum\limits_{d=0}^n E(d^k)\newline &= \sum\limits_{d=0}^n P(d)·d^k\newline &= \sum\limits_{d=0}^n\dbinom{n}{d}\left(\frac{1}{m}\right)^d\left(1-\frac{1}{m} \right)^{n-d} ·d^k \end{aligned}$$ 把后面的 $d^k$ 拿 Stirling 数展开，大力化一下柿子，得到：
$$ \sum\limits_{d=0}^n\dbinom{n}{d}\left(\frac{1}{m}\right)^d\left(1-\frac{1}{m} \right)^{n-d} ·d^k=\sum\limits_{i=0}^k \begin{Bmatrix}k\newline i\end{Bmatrix} n^{\underline{i}}\left(\frac{1}{m} \right)^i $$ 就可以做了，时间复杂度 $O(k^2)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int P = 998244353;
const int CN = 5005;

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

int n, m, k, S[CN][CN], ans = 0;

int main()
{
    n = read(), m = read(), k = read(), m = qp(m, P - 2);

    S[0][0] = 1;
    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= i; j++) S[i][j] = (1ll * j * S[i - 1][j] % P + S[i - 1][j - 1]) % P;

    int fall = 1, pw = 1;
    for(int i = 0; i <= k; i++){
        int prd = 1ll * S[k][i] * fall % P;
        ans = (1ll * prd * pw % P + ans) % P;
        pw = 1ll * pw * m % P, fall = 1ll * fall * (n - i) % P;
    }

    printf("%d", ans);
}