一些水题，部分结合了基础的高斯消元
收集邮票
题面
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 |
|
[六省联考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 |
|
[国家集训队]单选错位
题面
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 |
|
[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 |
|
[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 |
|
[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 |
|
神仙题
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 |
|