4

「专题选做」概率与期望题目选做 1

 2 years ago
source link: https://blunt-axe.github.io/2019/12/09/20191209-Probability-and-Expectation-1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

TorusSailing

「Topcoder 12984」TorusSailing

有 的网格，一人从 随机游走，每次等概率向下或向右，问走到 的期望步数。

数据范围：。

表示 走左、上游走到 的期望时间。发现所有两维坐标都 的 都可以用 和 的线性组合表出，于是我们列出关于 和 的方程并用高斯消元解出即可，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef double db;
5
const int maxn = 200;
6
7
class TorusSailing {
8
public:
9
	int n, m, x, y;
	db a[maxn + 3][maxn + 3][maxn + 3], f[maxn + 3][maxn + 3], res[maxn + 3];
	void gauss(db a[][maxn + 3], int n) {
		for (int i = 1; i <= n; i++) {
			int id = i;
			for (int j = i + 1; j <= n; j++) {
				if (a[j][i] > a[id][i]) id = j;
			}
			if (id != i) {
				swap(a[id], a[i]);
20
			}
21
			for (int j = i + 1; j <= n; j++) {
22
				db t = a[j][i] / a[i][i];
23
				for (int k = i; k <= n; k++) {
24
					a[j][k] -= t * a[i][k];
25
				}
26
				a[j][0] -= t * a[i][0];
27
			}
28
		}
29
		for (int i = n; i; i--) {
30
			res[i] = a[i][0] / a[i][i];
31
			for (int j = 1; j < i; j++) {
32
				a[j][0] -= res[i] * a[j][i];
33
			}
34
		}
35
	}
36
37
	db expectedTime(int N, int M, int X, int Y) {
38
		n = N, m = M, x = X + 1, y = Y + 1;
39
		for (int i = 2; i <= n; i++) {
40
			a[i][1][i - 1] = 1;
41
		}
42
		for (int i = 2; i <= m; i++) {
43
			a[1][i][i + n - 2] = 1;
44
		}
45
		for (int i = 2; i <= n; i++) {
46
			for (int j = 2; j <= m; j++) {
47
				for (int k = 0; k <= n + m - 2; k++) {
48
					a[i][j][k] = (a[i - 1][j][k] + a[i][j - 1][k]) / 2;
49
				}
50
				a[i][j][0] += 1;
51
			}
52
		}
53
		for (int i = 2; i <= n; i++) {
54
			db *g = f[i - 1];
55
			g[i - 1] = 2;
56
			for (int j = 0; j <= n + m - 2; j++) {
57
				g[j] -= a[i - 1][1][j] + a[i][m][j];
58
			}
59
			g[0] = -g[0] + 2;
60
		}
61
		for (int i = 2; i <= m; i++) {
62
			db *g = f[i + n - 2];
63
			g[i + n - 2] = 2;
64
			for (int j = 0; j <= n + m - 2; j++) {
65
				g[j] -= a[1][i - 1][j] + a[n][i][j];
66
			}
67
			g[0] = -g[0] + 2;
68
		}
69
		gauss(f, n + m - 2);
70
		db ans = 0;
71
		for (int i = 1; i <= n + m - 2; i++) {
72
			ans += res[i] * a[x][y][i];
73
		}
74
		ans += a[x][y][0];
75
		return ans;
76
	}
77
};

「HDU 4035」Maze

给定一棵 个点的树，一个人在 ，每次有 的概率传送回 ，有 的概率逃出，有 的概率随机游走到邻居。问逃出时走过边数的期望。

数据范围：。

表示从 出发经过边数的期望。记 表示 的父亲， 表示 的度数，那么有：

更具体地，对于非根结点 ，有：

对于根结点 ，有：

可以把每个点表示成一个三元组 表示 ，然后在树上自底向上消元。注意对根结点要特判，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef double db;
5
const int maxn = 1e4;
6
const db eps = 1e-9; // eps = 1e-8 wa
7
int T, n, d[maxn + 3];
8
db k[maxn + 3], e[maxn + 3], a[maxn + 3], b[maxn + 3], c[maxn + 3], ans;
9
bool flag;
vector<int> G[maxn + 3];
void add(int u, int v) {
	G[u].push_back(v);
}
void dfs(int u, int pa = 0) {
	for (int i = 0, v; i < G[u].size(); i++) {
		v = G[u][i];
		if (v == pa) continue;
20
		dfs(v, u);
21
	}
22
	if (u == 1) {
23
		db t = (1 - k[u] - e[u]) / d[u];
24
		db p = 1 - k[u], q = 1 - k[u] - e[u];
25
		for (int i = 0, v; i < G[u].size(); i++) {
26
			v = G[u][i];
27
			if (v == pa) continue;
28
			p -= t * (a[v] + b[v]), q += t * c[v];
29
		}
30
		if (fabs(p) < eps) {
31
			flag = false;
32
		} else {
33
			ans = q / p;
34
		}
35
	} else {
36
		db t = (1 - k[u] - e[u]) / d[u];
37
		a[u] = k[u], b[u] = t, c[u] = 1 - k[u] - e[u];
38
		db p = 1;
39
		for (int i = 0, v; i < G[u].size(); i++) {
40
			v = G[u][i];
41
			if (v == pa) continue;
42
			a[u] += t * a[v], c[u] += t * c[v];
43
			p -= t * b[v];
44
		}
45
		if (fabs(p) < eps) {
46
			flag = false;
47
		} else {
48
			p = 1 / p;
49
			a[u] *= p, b[u] *= p, c[u] *= p;
50
		}
51
	}
52
}
53
54
int main() {
55
	scanf("%d", &T);
56
	for (int _ = 1; _ <= T; _++) {
57
		printf("Case %d: ", _);
58
		scanf("%d", &n);
59
		for (int i = 1; i <= n; i++) {
60
			vector<int>().swap(G[i]), d[i] = 0;
61
		}
62
		for (int i = 1, u, v; i < n; i++) {
63
			scanf("%d %d", &u, &v);
64
			add(u, v), add(v, u), d[u]++, d[v]++;
65
		}
66
		for (int i = 1; i <= n; i++) {
67
			scanf("%lf %lf", &k[i], &e[i]);
68
			k[i] /= 100, e[i] /= 100;
69
		}
70
		flag = true;
71
		dfs(1);
72
		if (flag) {
73
			printf("%.6f\n", ans);
74
		} else {
75
			puts("impossible");
76
		}
77
	}
78
	return 0;
79
}

分手是祝愿

「LOJ 2145」分手是祝愿

有 个灯泡，给定它们的明暗状态。还有 个开关，第 个按下后就把编号为它的所有因数的灯泡取反，一个人随机操作开关，直到有一种方案操作 次把所有灯变暗时采用最优策略，问期望操作次数。

数据范围：。

根据灯泡的明暗序列我们可以直接推出最优的操作序列，于是问题就变成给定 01 串，每次选一个位置取反，直到有 个 1 时停止。记 表示从 个 1 变成 个 1 的期望步数，那么有：

干就完了，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e5, mod = 1e5 + 3;
5
int n, k, a[maxn + 3], c, f[maxn + 3];
6
7
int qpow(int a, int b) {
8
	int c = 1;
9
	for (; b; b >>= 1, a = 1ll * a * a % mod) {
		if (b & 1) c = 1ll * a * c % mod;
	}
	return c;
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
20
	for (int i = n; i; i--) if (a[i]) {
21
		c++;
22
		for (int j = 1; j * j < i; j++) {
23
			if (i % j == 0) a[j] ^= 1;
24
		}
25
		for (int j = 1; j * j <= i; j++) {
26
			if (i % j == 0) a[i / j] ^= 1;
27
		}
28
	}
29
	for (int i = 1; i <= k; i++) {
30
		f[i] = i;
31
	}
32
	for (int i = n; i > k; i--) {
33
		f[i] = (1ll * (n - i) * f[i + 1] + n) * qpow(i, mod - 2) % mod;
34
	}
35
	for (int i = k + 1; i <= n; i++) {
36
		f[i] = (f[i - 1] + f[i]) % mod;
37
	}
38
	int ans = f[c];
39
	for (int i = 1; i <= n; i++) {
40
		ans = 1ll * ans * i % mod;
41
	}
42
	printf("%d\n", ans);
43
	return 0;
44
}

「Luogu 4548」歌唱王国

给定长度为 的串，有空串 ，每次在 末尾加入一个 的字符，直到 的后缀为给定串时停止。问 的期望长度。

数据范围：。

记 表示 为 的概率，那么 时 ， 时有转移方程：

令 ，那么有 。我们把它代入 的转移方程得到：

我们要求的是 ，也就是 。把 的生成函数记为 ，那么我们求的就是 。将转移方程改写，得：

用 KMP 求出 ，直接计算，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 1e5, mod = 1e4;
5
int T, m, n, p[maxn + 3], a[maxn + 3], nxt[maxn + 3];
6
7
int main() {
8
	scanf("%d %d", &m, &T);
9
	p[0] = 1;
	for (int i = 1; i <= maxn; i++) {
		p[i] = p[i - 1] * m % mod;
	}
	while (T --> 0) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 2, k = 0; i <= n; i++) {
			while (k && a[k + 1] != a[i]) k = nxt[k];
20
			if (a[k + 1] == a[i]) k++;
21
			nxt[i] = k;
22
		}
23
		int ans = 0;
24
		for (int k = n; k; k = nxt[k]) {
25
			ans += p[k];
26
		}
27
		ans %= mod;
28
		printf("%04d\n", ans);
29
	}
30
	return 0;
31
}

「Luogu 3706」硬币游戏

有 个人，每个人有一个长度为 的 01 串。在初始为空的串 末尾随机加入 0 或 1，直到 的后缀是某个 01 串为止，持有该串的人胜利。问最终每个人胜利的概率。

数据范围：。

01 串可以分为三类：未终止态，终止态，非法态。记 表示所有未终止态的概率和， 表示 胜利的概率。拿样例举例，，三个串为 THT, TTH, HTT，我们考虑 。首先随便选一个串后面加上 TTH，概率是 。发现有可能提前变成终止态，如果在加第一个字符时变成终止态，原串的一定是 TH，HT 结尾的，所以概率是 。同理，如果在加第二个字符时变成终止态，概率是 。所以有 。类似地可以列出 个方程，最后再外加一个 ，用高斯消元解方程即可。时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef double db;
5
const int maxn = 300, mod = 987898789;
6
int n, m, bin[maxn + 3], a[maxn + 3][maxn + 3];
7
char s[maxn + 3][maxn + 3];
8
db num[maxn + 3], f[maxn + 3][maxn + 3], res[maxn + 3];
9
int value(int x, int l, int r) {
	return (a[x][r] + 1ll * (mod - a[x][l - 1]) * bin[r - l + 1]) % mod;
}
void gauss(db a[][maxn + 3], int n) {
	for (int i = 1; i <= n; i++) {
		int id = i;
		for (int j = i + 1; j <= n; j++) {
			if (fabs(a[j][i]) > fabs(a[id][i])) id = j;
		}
20
		if (id != i) {
21
			swap(a[id], a[i]);
22
		}
23
		for (int j = i + 1; j <= n; j++) {
24
			db t = a[j][i] / a[i][i];
25
			for (int k = i; k <= n; k++) {
26
				a[j][k] -= t * a[i][k];
27
			}
28
			a[j][0] -= t * a[i][0];
29
		}
30
	}
31
	for (int i = n; i; i--) {
32
		res[i] = a[i][0] / a[i][i];
33
		for (int j = 1; j < i; j++) {
34
			a[j][0] -= res[i] * a[j][i];
35
		}
36
	}
37
}
38
39
int main() {
40
	scanf("%d %d", &n, &m);
41
	bin[0] = 1, num[0] = 1;
42
	for (int i = 1; i <= m; i++) {
43
		bin[i] = (bin[i - 1] * 2) % mod;
44
		num[i] = num[i - 1] / 2;
45
	}
46
	for (int i = 1; i <= n; i++) {
47
		scanf("%s", s[i] + 1);
48
		for (int j = 1; j <= m; j++) {
49
			a[i][j] = (a[i][j - 1] * 2 + (s[i][j] == 'H')) % mod;
50
		}
51
	}
52
	for (int i = 1; i <= n; i++) {
53
		f[i][n + 1] = -num[m];
54
		for (int j = 1; j <= n; j++) {
55
			for (int k = 1; k <= m; k++) {
56
				if (value(i, 1, k) == value(j, m - k + 1, m)) {
57
					f[i][j] += num[m - k];
58
				}
59
			}
60
		}
61
	}
62
	for (int i = 0; i <= n; i++) {
63
		f[n + 1][i] = 1;
64
	}
65
	gauss(f, n + 1);
66
	for (int i = 1; i <= n; i++) {
67
		printf("%.9lf\n", res[i]);
68
	}
69
	return 0;
70
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK