概率与期望
目录
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄
概率与期望
1. 算法分析
数学期望的性质
- 设X是随机变量，C是常数，则E（CX）=CE（X）。
- 设X，Y是任意两个随机变量，则有E（X+Y）=E（X）+E（Y）。
- 设X，Y是相互独立的随机变量，则有E（XY）=E（X）E（Y）。
- 设C为常数，则E（C）=C。
特点分析
数学期望的题目一般都是DAG，起点唯一，终点很多的情况，这种情况下一般都是dp处理，从终点往起点做dp，答案就是f[1].
解法可以直接递推：反向建图，然后topsort跑出拓扑序，按照拓扑序做dp；
也可以记忆化搜索，直接正向做记忆化搜索。
规律总结
这里要注意的一点：
随机变量X = Y1+Y2+Y3+...+Yn(认为Yi里面有ti个元素)
按照公式E(X) = E(Y1)+E(Y2)+...+E(Yn)
可是一般计算的时候都是dp[x] = dp[y1]p1+dp[y2]p2+...为什么呢？
因为递推的过程中，算出dp[y1]时是认为只有t1个元素，而在算dp[x]时，元素个数是t1+t2+t3+...+tn个，所以要把原来算出来的期望dp[y1] * p1表示原先算出来的期望E'需要先转化为当前期望E,二者的转换关系为E' * p1=E
因此，我们可以得出结论：
从起点开始递推，当前的期望=累加【子状态的期望 * 子状态出现的概率】
2. 例题
2.1 期望的线性
bzoj2969矩形粉刷
小M粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具，这个工具只需要指定方阵中两个格子，就可以把这两格子为对角的，平行于木板边界的一个子矩形全部刷好。小M乐坏了，于是开始胡乱地使用这个工具。假设小M每次选的两个格子都是完全随机的（方阵中每个格子被选中的概率是相等的），而且小M使用了K次工具，求木板上被小M粉刷过的格子个数的期望值是多少。
/* 由于期望具有可加性，因此可以计算出每个格子被染色的概率，加起来即为答案。
那么一个格子被染色的概率即为1-(每次都不被染色的概率)^k。
考虑单次染色没有没染的情况：选定的两个点都在左边、上边、右边、下边，但是会发现四个角的部分会计算两次，因此还需要减掉两个点都在左上、左下、右上、右下的情况。然后求幂加起来即可。 */
#include <cmath>
#include <cstdio>
inline double squ(double x)
{
return x * x;
}
int main()
{
int k , n , m , i , j;
double ans = 0;
scanf("%d%d%d" , &k , &n , &m);
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= m ; j ++ )
ans += 1 - pow((squ((i - 1) * m) + squ((j - 1) * n) + squ((n - i) * m) + squ((m - j) * n)
- squ((i - 1) * (j - 1)) - squ((i - 1) * (m - j)) - squ((n - i) * (j - 1)) - squ((n - i) * (m - j))) / squ(n * m) , k);
printf("%.0lf\n" , ans);
return 0;
}
2.2 DAG期望
acwing217绿豆蛙的归宿
一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？
N~1e5, M~2N
#include <bits/stdc++.h>
using namespace std;
int const N = 1e5 + 10;
int n, m, dout[N], e[N * 2], ne[N * 2], idx, h[N], w[N * 2];
double f[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
double dp(int u)
{
if (f[u] >= 0) return f[u]; // 搜索过了
f[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) // 遍历所有后继
{
int j = e[i];
f[u] += (w[i] + dp(j)) / dout[u]; // 当前状态的期望=所有子状态期望 * 对应概率
}
return f[u];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1, a, b, c; i <= m; ++i) {
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
dout[a]++;
}
memset(f, -1, sizeof f);
printf("%.2lf", dp(1));
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int const N = 1e5 + 10;
int n, m, h[N], e[N * 2], ne[N * 2], idx, w[N * 2], din[N], d[N], a[N], cnt;
double f[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void top_sort() {
queue<int> q;
q.push(n); // 一开始只需要把n放进去即可
while (q.size())
{
auto t = q.front();
q.pop();
a[cnt++] = t;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
d[j]--;
if (!d[j]) q.push(j);
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
// 反向建图
for (int i = 1, a, b, c; i <= m; ++i) {
cin >> a >> b >> c;
add(b, a, c);
din[a]++;
}
memcpy(d, din, sizeof d); // 复制din，因为拓扑排序会改变din
top_sort(); // 得到拓扑序
// 按照拓扑序做dp更新
for (int i = 0; i < cnt; ++i)
{
int t = a[i];
for (int j = h[t]; ~j; j = ne[j])
{
int k = e[j];
f[k] += (w[j] + f[t]) / din[k];
}
}
printf("%.2lf", f[1]);
return 0;
}
2.3 无向图期望
【bzoj3143】[Hnoi2013]游走
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
/* 显然让期望经过次数越大的边编号越小即可，所以只要求出边的期望经过次数就能出解。
由于边数过大，但是边的期望经过次数可以用它连接的两个点的 期望次数/度数 之和得到，所以只要求出点的期望经过次数就能出解。
对于每个一般的点y，它的期望经过次数为f[y]=∑exist x→y f[x] / d[x]。
然后有两个特殊的点：1和n，由于1是起点，所以要算上初始经过的一次，在表达式的右边加1；由于n是终点，到达终点就不能够再经过其它边，所以按照上面的期望经过次数的计算方式，n的期望经过次数应该强制设置为0。（并非部分题解中的1）（所以其实上面的期望经过次数指的是“到达终点前的期望经过次数”，实际上也应该这样理解）
由于图是没有dp顺序的，所以需要使用高斯消元求出f[i]。
求出所有点的期望经过次数，然后计算出边的经过次数，排序出解。 */
#include <bits/stdc++.h>
using namespace std;
int const N = 510;
const double eps = 1e-11;
int mp[N][N], n, m, d[N];
double a[N][N];
struct Edge {
int u, v;
double val;
bool operator<(const Edge &w) const{
return val > w.val;
}
}edge[200010];
void gauss(int m, int n)
{
int c, r;
for (c = 0, r = 0; c < n && r < m; c ++, r++) // 正在找第i元
{
// 找出第一个元素最大的那一行
int t = r;
for (int i = r; i < m; i ++ )
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) {
r--;
continue; // 如果是0，那么不用管
}
for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]); // 把第一个元素最大的那一行放到第一行
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 把第一行的首元消成1
for (int i = r + 1; i < m; i ++ ) // 把后面每行都和刚刚首元消成1的那行做运算
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
}
// 唯一解，把解放到n+1列
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[j][n] * a[i][j];
return ;
}
int main() {
cin >> n >> m;
for (int i = 1, a, b; i <= m; ++i) {
scanf("%d%d", &a, &b);
edge[i].u = a, edge[i].v = b;
mp[a][b] = mp[b][a] = 1;
d[a]++, d[b]++;
}
for(int i = 1; i < n; i ++)
{
a[i - 1][i - 1] = 1;
for(int j = 1; j <= n; j ++) if(mp[j][i]) a[i - 1][j - 1] = -1.0 / (double)d[j];
}
a[0][n] = a[n - 1][n - 1] = (double)1;
gauss(n, n);
for(int i = 1 ; i <= m ; i ++ ) edge[i].val = a[edge[i].u - 1][n] / (double)d[edge[i].u] + a[edge[i].v - 1][n] / (double)d[edge[i].v];
sort(edge + 1, edge + m + 1);
double res = 0;
for (int i = 1; i <= m; ++i) res += edge[i].val * i;
printf("%.3lf", res);
return 0;
}
更多精彩
