常见模型技巧总结
概率正推，期望倒推
简单概率期望
- 简单分类讨论。P1297 [国家集训队]单选错位
- 根据题目推导。UVA11021 Tribles
需要一些小观察的题目
- 01最终位置确定，倒推期望。CF1754E. Wish I Knew How to Sort
图上概率期望
- 简单拓扑排序+期望。P6154 游走
习题
洛谷
P6154 游走
题意
B 城可以看作一个有 \(n\;(n\leq 10^5)\) 个点 \(m\) 条边的有向无环图。可能存在重边。
zbw 在 B 城随机游走，他会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。
定义一条路径的长度为经过的边数，你需要求出 zbw 走的路径长度的期望，答案对 \(998244353\) 取模。
思路
- 注意题目要求的东西，路径长度的期望等于 总长度 / 路径数。
- \(f_i\) i 结尾的路径长度总和， \(g_i\) i 结尾的路径条数。
- \(g_i = \sum{edge(j,i)} g_j\) \(f_i = \sum_{edge(j,i)} f_j + g_j\) 。
- 边界 \(g_i = 1\) ，答案等于 \(\frac{\sum_i f_i}{\sum_i g_i}\) ，快速幂做逆元。
P1297 [国家集训队]单选错位
题意
\(n\leq 10^7\) 个选择题，每个选择题有 \(a_i\) 个答案，每道题的答案是上一道题的正确答案，询问期望做对的题目数量。
思路
- 分类讨论：
- \(a[i]=a[i-1]\) ，和随机选答案做对期望一样，\(\frac{1}{a_i} \times 1 = \frac{1}{a_i}\)
- \(a[i] > a[i - 1]\) ，有 \(\frac{a_{i-1}}{a_i}\) 的概率答案在前一个范围内的数，在 i - 1 项有 \(\frac{1}{a_{i-1}}\) 的概率选到正确答案，答案为 \(\frac{1}{a_i}\) 。
- \(a[i] < a[i - 1]\) ，同理答案为 \(\frac{1}{a_{i-1}}\) 。
UVA11021 Tribles
题意
一开始有 \(k\) 种生物，这种生物只能活1天，死的时候有 \(p_i\) 的概率产生 \(i\)只这种生物（也只能活一天），询问 \(m\) 天内所有生物都死的概率（包括 \(m\) 天前死亡的情况）。
思路
- \(dp[i]\) 表示对于某一只生物第 i 天消亡的概率，最后的答案算下 k 次幂就可以了。
- 考虑接下来生 j 只生物，其消亡概率为 \(dp[i] = \sum_{j<n} p[j]\times dp[j]^k\) ，复杂度 \(O(nm)\) 。
Codeforces
CF768D. Jon and Orbs
CF768D 、概率DP、
给 \(k\) 种龙晶，\(q\) 个询问，每天产生一种龙晶，且概率相等，每次询问一个 \(p\)，求产生 \(k\) 种龙晶的概率 \(\geq \frac{p-ε}{2000}\) 的最小天数。
- 简单概率DP，设状态为 \(dp[i][j]\) 第 i 天产生 j 种龙晶
- 很容易转移。其中边界是
dp[i][0] = (i == 0) ? 1 : 0; - 由于不知道最小天数，并且 p 和最小天数有单调性，所以直接滚动数组，预处理询问答案。
const int N = 1010;
int ans[N];
double dp[N];
int main() {
int k, q;
re(k), re(q);
dp[0] = 1;
for (int i = 1, p = 1; p <= 1000; i++) {
for (int j = k; j; j--)
dp[j] = dp[j] * j / k + dp[j - 1] * (k - (j - 1)) / k;
while (p <= 1000 && dp[k] * 2000 >= p - 1e-7) ans[p++] = i;
dp[0] = 0;
}
while (q--) {
int x;
re(x);
printf("%d\n", ans[x]);
}
return 0;
}
CF1754E. Wish I Knew How to Sort
题意
长为 \(n\) 的 01 数组，每次随机选取一对位置交换，如果 1 在前就交换两个元素，询问选取次数的期望使数组排好序？
思路
- 一个观察，0 和 1 的位置在排好序以后是固定的，只需要有多少个位置应该是 1 但现在是 0。
- 统计之后，以 \(f_i\) 表示有 i 对位置还需要交换。
- 期望倒推转移: \(f_i = \frac{i\times i}{n\times (n-1)} \times f_{i-1} + (1 - \frac{i\times i}{n\times (n-1)}) * f_i + 1\)
- 即 \(f_i = f_{i-1} + \frac{n\times (n-1)}{i*i}\)