期望入门

一些水题,部分结合了基础的高斯消元

收集邮票

题面

Solution

$f[i]$:已获得$i$种邮票,买完剩下的需要的期望次数

$\frac{i}{n}$的概率取到已有的,接下去仍需取$f[i]$次

$\frac{n - i}{n}$的概率取到未取过的,接下去需取$f[i + 1]$次

最后要加上这一次取的$1$次
$$
f[i] = \begin{cases}
0 & (i == n) \
\frac{i}{n} \times f[i] + \frac{n - i}{n} \times f[i + 1] + 1 & (0 \le i \lt n)
\end{cases}
$$

$$
f[i] = f[i + 1] + \frac{n}{n - i}
$$
$g[i]$:已获得$i$种邮票,买完剩下的需要的期望代价

$\frac{i}{n}$的概率取到已有的,还需要$g[i]$的代价,这对之后所有的$f[i]$次都会增加$1$的代价,还要加上这一次的代价$1$

$\frac{n - i}{n}$的概率取到未取过的,同上
$$
g[i] = \begin{cases}
0 & (i == n) \
\frac{i}{n} \times (g[i] + f[i] + 1) + \frac{n - i}{n} \times (g[i + 1] + f[i + 1] + 1) & (0 \le i \lt n)
\end{cases}
$$

$$
g[i] = \frac{i}{n - i}\times f[i] + g[i + 1] + f[i + 1] + \frac{n}{n - i}
$$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>

const int N = 1e4;
int n;
double f[N + 5], g[N + 5];

int main() {
scanf("%d", &n);
for (int i = n - 1; i >= 0; --i) {
f[i] = f[i + 1] + 1.0 * n / (n - i);
g[i] = 1.0 * i / (n - i) * f[i] + g[i + 1] + f[i + 1] + 1.0 * n / (n - i);
}
printf("%.2lf\n", g[0]);
return 0;
}

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

题面

Solution

首先发现如果每个开关最多按一次,那么要按的开关是哪些就是确定的

于是我们可以从$n$到$1$扫一遍将它们找出来,记个数为$num$

$dp[i]$表示从$i$个开关要按的状态到$(i - 1)$个开关要按的状态的期望次数

考虑$dp[i]$,即有$i$个开关要按

$i / n$的概率按对,$(n - i) / n$的概率按错

按对的期望是$1$次$($到$i - 1$$)$,按错的期望是$(1 + dp[i + 1] + dp[i])$次$($分别表示错按的一次、按回来的$dp[i + 1]$次以及再按到$(i - 1)$的$dp[i]$次$)$

那么有
$$
dp[i] = \frac {i} {n} + \frac {n - i} {n} \times (1 + dp[i + 1] + dp[i])
$$
化简后得
$$
dp[i] = \frac {n + (n - i) \times dp[i + 1]} {i}
$$
边界$dp[n] = 1$

最后统计答案:如果$num \le K$,那么答案为$num$,否则答案为$\sum ^{num} _{i = K + 1} dp[i]$

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
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e5, Mod = 1e5 + 3;
int n, K, num, a[N + 5], Inv[N + 5], dp[N + 5], ans;

int main() {
scanf("%d%d", &n, &K);
Inv[1] = 1;
for (int i = 2; i <= n; ++i)
Inv[i] = 1LL * (Mod - Mod / i) * Inv[Mod % i] % Mod;
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = n; i >= 1; --i)
if (a[i] == 1) {
++num;
for (int j = 1; j * j <= i; ++j)
if (i % j == 0) {
a[j] ^= 1;
if (j * j != i) a[i / j] ^= 1;
}
}
dp[n] = 1;
for (int i = n - 1; i >= 1; --i)
dp[i] = 1LL * (n + 1LL * (n - i) * dp[i + 1] % Mod) * Inv[i] % Mod;
if (num <= K) ans = num;
else {
for (int i = K + 1; i <= num; ++i)
ans = (ans + dp[i]) % Mod;
ans = (ans + K) % Mod;
}
for (int i = 1; i <= n; ++i) ans = 1LL * ans * i % Mod;
printf("%d\n", ans);
return 0;
}

[国家集训队]单选错位

题面

Solution

由于不同题目的选择之间不会有影响,我们可以考虑对每题的贡献分别计算

  • $a_i \ge a_{i - 1}$,那么前一题无论选什么这一题都会有这个选项,这一题的答案落在$[1, a_{i - 1}]$之间的概率为$\frac {a_{i - 1}} {a_i}$,在此前提下与前一题答案一致的概率为$\frac {1} {a_{i - 1}}$,两者相乘得$\frac {1} {a_i}$
  • $a_i \lt a_{i - 1}$,那么前一题的答案落在$[1, a_i]$之间的概率为$\frac {a_i} {a_{i - 1}}$,在此前提下与这一题答案一致的概率为$\frac {1} {a_i}$,两者相乘得$\frac {1} {a_{i - 1}}$

综上所述,第$i$题正确的概率为
$$
f_i = \begin{cases}
\frac {1} {a_i} & a_i \ge a_{i - 1} \
\frac {1} {a_{i - 1}} & a_i \lt a_{i - 1}
\end{cases}
$$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
#define LL long long

const int Mod = 1e8 + 1;
int n, A, B, C, a;
double ans;

int main() {
scanf("%d%d%d%d%d", &n, &A, &B, &C, &a);
int tmp = a, last = a % C + 1;
for (int i = 2; i <= n; ++i) {
tmp = 1LL * (1LL * tmp * A + B) % Mod;
int cur = tmp % C + 1;
ans += cur >= last ? 1.0 / cur : 1.0 / last;
last = cur;
}
int cur = a % C + 1;
ans += cur >= last ? 1.0 / cur : 1.0 / last;
printf("%.3lf\n", ans);
return 0;
}

[HNOI2013]游走

题面

Solution

$f[i]$为$i$号点期望经过次数,$deg[i]$表示$i$号点度数

注意一旦到达$n$号点后便不再返回
$$
f[i] = \sum _{j | (i,j) \in E, j \ne n} \frac {f[j]} {deg[j]}
$$

$$
\sum _{j | (i,j) \in E, j \ne n} \frac {f[j]} {deg[j]} - f[i] = 0
$$

特殊地,$1$号点有$1$次的初始值
$$
f[1] = 1 + \sum _{j | (1,j) \in E, j \ne n} \frac {f[j]} {deg[j]}
$$

$$
\sum _{j | (1,j) \in E, j \ne n} \frac {f[j]} {deg[j]} - f[1] = -1
$$

进行高斯消元后,$g[i]$为$i$号边期望经过次数
$$
g[i] = \frac {f[u]} {deg[u]} + \frac {f[v]} {deg[v]}
$$
显然期望经过次数越多的边应赋越小的值

将所有边按期望经过次数降序排序后,答案为
$$
ans = \sum _{i = 1} ^m i \times g[i]
$$

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
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 5e2;
const double eps = 1e-8;
int n, m, deg[N + 2], U[N * N + 2], V[N * N + 2];
double f[N + 2][N + 2], res[N + 2], ans, g[N * N + 2];
std::vector <int> E[N + 2];

inline void Gauss() {
for (int i = 1; i <= n; ++i) {
int cur = i;
for (int j = i + 1; j <= n; ++j)
if (fabs(f[j][i]) > fabs(f[cur][i]))
cur = j;
if (fabs(f[cur][i]) < eps) continue;
std::swap(f[i], f[cur]);
double div = f[i][i];
for (int j = i; j <= n + 1; ++j)
f[i][j] /= div;
for (int j = i + 1; j <= n; ++j) {
double div = f[j][i] / f[i][i];
for (int k = i; k <= n + 1; ++k)
f[j][k] -= div * f[i][k];
}
}
for (int i = n; i >= 1; --i) {
for (int j = i + 1; j <= n; ++j)
f[i][n + 1] -= res[j] * f[i][j];
res[i] = f[i][n + 1];
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &U[i], &V[i]);
++deg[U[i]], ++deg[V[i]];
E[U[i]].push_back(V[i]), E[V[i]].push_back(U[i]);
}
f[1][n + 1] = -1;
for (int i = 1; i < n; ++i) {
f[i][i] = -1;
for (int j = 0; j < (int) E[i].size(); ++j)
f[i][E[i][j]] = 1.0 / deg[E[i][j]];
f[i][n] = 0;
}
Gauss();
for (int i = 1; i <= m; ++i)
g[i] = res[U[i]] / (double) deg[U[i]] + res[V[i]] / (double) deg[V[i]];
std::sort(g + 1, g + 1 + m);
for (int i = 1; i <= m; ++i)
ans += (m - i + 1) * g[i];
printf("%.3lf\n", ans);
return 0;
}

[USACO10HOL]赶小猪

题面

Solution

考虑类似的做法
$$
f[i] = \sum _{j | (i, j) \in E} (1 - \frac {p} {q}) \times \frac {f[j]} {deg[j]} + [i== 1]
$$
答案
$$
ans[i] = \frac {p} {q} \times f[i]
$$

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
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 5e2;
const double eps = 1e-8;
int n, m, deg[N + 2], U[N * N + 2], V[N * N + 2];
double p, q, f[N + 2][N + 2], res[N + 2], ans, g[N * N + 2];
std::vector <int> E[N + 2];

inline void Gauss() {
for (int i = 1; i <= n; ++i) {
int cur = i;
for (int j = i + 1; j <= n; ++j)
if (fabs(f[j][i]) > fabs(f[cur][i]))
cur = j;
if (fabs(f[cur][i]) < eps) continue;
std::swap(f[i], f[cur]);
double div = f[i][i];
for (int j = i; j <= n + 1; ++j)
f[i][j] /= div;
for (int j = i + 1; j <= n; ++j) {
double div = f[j][i] / f[i][i];
for (int k = i; k <= n + 1; ++k)
f[j][k] -= div * f[i][k];
}
}
for (int i = n; i >= 1; --i) {
for (int j = i + 1; j <= n; ++j)
f[i][n + 1] -= res[j] * f[i][j];
res[i] = f[i][n + 1];
}
}

int main() {
scanf("%d%d%lf%lf", &n, &m, &p, &q);
p /= q;
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
++deg[u], ++deg[v];
E[u].push_back(v), E[v].push_back(u);
}
f[1][n + 1] = -1;
for (int i = 1; i <= n; ++i) {
f[i][i] = -1;
for (int j = 0; j < (int) E[i].size(); ++j)
f[i][E[i][j]] = (1.0 - p) / deg[E[i][j]];
}
Gauss();
for (int i = 1; i <= n; ++i)
printf("%.9lf\n", p * res[i]);
return 0;
}

[HNOI2011]XOR和路径

题面

Solution

比较套路

首先必须明白的一点是,直接做显然行不通你看你都不知道实数下的异或是个啥对吧,但因为异或运算的特殊性,我们可以将每一位分开考虑

$f_i$表示从$i$到$n$路径上这一位的异或期望值,即为$1$的概率,$deg_i$表示度数
$$
f_i = \frac {1} {deg_i} (\sum _{w(i,j) = 0} f_j + \sum _{w(i,j) = 1}(1 - f_j))
$$

$$
deg_i \times f_i - \sum _{w(i,j) = 0}f_j + \sum _{w(i,j) = 1}f_j = \sum _{w(i,j) = 1}
$$

直接高斯消元,注意不能把$n$号点的贡献算上
$$
ans = \sum _{i = 0} ^ {30} 2^i \times f_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
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
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e2;
const double eps = 1e-8;
int n, m, deg[N + 5];
double a[N + 5][N + 5], res[N + 5], ans;
struct Edge {
int v, w;
Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};
std::vector <Edge> E[N + 5];

inline void Gauss() {
for (int i = 1; i <= n; ++i) {
int cur = i;
for (int j = i + 1; j <= n; ++j)
if (fabs(a[j][i]) > fabs(a[cur][i]))
cur = j;
if (fabs(a[cur][i]) < eps) continue;
std::swap(a[cur], a[i]);
double div = a[i][i];
for (int j = i; j <= n + 1; ++j)
a[i][j] /= div;
for (int j = i + 1; j <= n; ++j) {
double div = a[j][i] / a[i][i];
for (int k = i; k <= n + 1; ++k)
a[j][k] -= div * a[i][k];
}
}
for (int i = n; i >= 1; --i) {
for (int j = i + 1; j <= n; ++j)
a[i][n + 1] -= a[i][j] * res[j];
res[i] = a[i][n + 1];
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
E[u].push_back(Edge(v, w));
++deg[u];
if (u != v) {
E[v].push_back(Edge(u, w));
++deg[v];
}
}
for (int i = 0; i <= 30; ++i) {
std::memset(a, 0, sizeof(a));
std::memset(res, 0, sizeof(res));
for (int j = 1; j < n; ++j) {
a[j][j] = (double)deg[j];
for (Edge e : E[j]) {
if (!((e.w >> i) & 1)) a[j][e.v] -= 1;
else {
a[j][e.v] += 1;
a[j][n + 1] += 1;
}
}
}
a[n][n] = 1;
Gauss();
ans += (1 << i) * res[1];
}
printf("%.3lf\n", ans);
return 0;
}

神仙题

Description

“德克萨斯那家伙能活得那么潇洒,可多亏了有我罩着她,这不是明摆着的事情嘛 ”

$\text{Texas}$和$\text{Exusiai}$两个人正在玩一个游戏,游戏有$n$种不同的关卡可以挑战,每次挑战需要消耗 1 点理智。对于关卡$i(1 ≤ i ≤ n)$,每个人都有相同的概率$p_i$成功完成任务并获得$1$点积分,有$1 − p_i$的概率行动失败不能获得任何奖励。两人的策略是使用所有理智每次等概率随机一个关卡挑战。现在$\text{Texas}$有$A$点理智,$\text{Exusiai}$有$B$点理智,他们想知道在两人的所有理智用完之后,$\text{Exusiai}$ 的积分严格大于$\text{Texas}$的概率模$10000019$ 意义下的值。

数据范围

$1 \le n, A \le 5 \times 10 ^ 6, 1 \le B \le 10 ^ {18}$

Solution

每轮胜利的概率为$P$,这个可以一开始就轻松求出

枚举$\text {Texas}$的得分$i$,恰好得$i$分的概率为
$$
P_i = \binom {A} {i} \cdot P ^ i \cdot (1 - P) ^ {A - i}
$$
$\text{Exusiai}$恰好得$i$分的概率为
$$
Q_i = \binom {B} {i} \cdot P ^ i \cdot (1 - P) ^ {B - i}
$$
那么$\text {Exusiai}$得至少$i + 1$分的概率为
$$
1 - \sum ^ i _ {j = 0} Q_j
$$
由于$\displaystyle\binom {B} {i}$不太好算$(A \le 5 \times 10^6)$,我们只能线性维护它

那么答案为
$$
\sum _{i = 0} ^{\min(A, B)} P_i \cdot(1 - \sum _{j = 0} ^i Q_j)
$$

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

inline int read() {
int x = 0; char c = getchar();
for (; c < 48 || c > 57; c = getchar());
for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
return x;
}

const int N = 5e6, Mod = 1e7 + 19;
int n, A, B, p[N + 5], fac[N + 5], ifac[N + 5], pow1[N + 5], pow2[N + 5], inv[N + 5];

inline int qpow(int x, int y) {
int res = 1;
for (; y; x = x * x % Mod, y >>= 1)
if (y & 1) res = res * x % Mod;
return res;
}

inline int Inv(int x) {
return qpow(x, Mod - 2);
}

inline int C(int n, int m) {
return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}

signed main() {
n = read(), A = read(), B = read();
int P = 0, Invn = Inv(n);
for (int i = 1; i <= n; ++i) {
int p = read();
P = (P + Invn * p) % Mod;
}
int Q = (1 + Mod - P) % Mod, InvQ = Inv(Q);
fac[0] = pow1[0] = pow2[0] = 1;
for (int i = 1; i <= A; ++i) {
fac[i] = fac[i - 1] * i % Mod;
pow1[i] = pow1[i - 1] * P % Mod;
pow2[i] = pow2[i - 1] * Q % Mod;
inv[i] = i == 1 ? 1 : (Mod - Mod / i) * inv[Mod % i] % Mod;
}
ifac[A] = Inv(fac[A]);
for (int i = A; i >= 1; --i)
ifac[i - 1] = ifac[i] * i % Mod;
int sum = 0, ans = 0, c = 1, pq = qpow(Q, B);
for (int i = 0; i <= std::min(A, B); ++i) {
int tmp = C(A, i) * pow1[i] % Mod * pow2[A - i] % Mod, ttmp = c * pq % Mod;
sum = (sum + ttmp) % Mod;
ans = (ans + tmp * (1 + Mod - sum) % Mod) % Mod;
c = (B - i) % Mod * c % Mod * inv[i + 1] % Mod;
pq = pq * InvQ % Mod * P % Mod;
}
printf("%lld\n", ans);
return 0;
}