AGC030D Inversion Sum
AtCoder Luogu 分析 设 $dp_{x,y}$ 表示 $a_x > a_y$ 的概率（假设每个操作发生的概率都为 $\frac{1}{2}$）。 对于每个操作 $(i,j)$，我们会让所有的 $dp_{i,k}$ 和 $dp_{j,k}$ 都变为 $\frac{1}{2}(dp_{i,k}+dp_{j,k})$，会让所有的 $dp_{k,i}$ 和 $dp_{k,j}$ 都...
标签 概率期望 下的文章
- 首页
- 概率期望
51nod1850 抽卡大赛
51nod 分析 首先考虑一个暴力做法。 假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。 枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移 这...
CF749E Inversions After Shuffle
Codeforces Luogu 分析 考虑一个点对 $(i,j)\;(i<j)$ 的贡献。 分两种情况考虑：$i,j$ 都在连续段内、$i,j$ 不都在连续段内。 先考虑第一种情况。显然连续段的左端点 $\in[1,i]$，右端点 $\in[j,n]$，于是随机出的连续段包含 $i,j$ 的概率为 那么对于每个 $i$，我们只要知道满足 $j>i,a_j<a_i$ 的...
CF1097D Makoto and a Blackboard
Codeforces Luogu 分析 容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小，转移直接枚举约数即可。然而这样子显然是会 T 的... 注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$，因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots...
UVA1498 Activation
UVa Luogu 分析 首先把 $p_4=0$ 的情况判掉，答案显然为 $0$ 。 考虑 DP 。设 $dp_{i,j}$ 表示 $i$ 个人的队列，现在在第 $j$ 个，最后在前 $k$ 个位置的概率。 转移可以考虑后继状态，容易得到 于是可以得到 $dp_{1,1}=\frac{p_4}{1-p_1-p_2}$ 。 具体实现及细节见代码。 代码 // ================...
洛谷3779 [SDOI2017]龙与地下城
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
洛谷3706 [SDOI2017]硬币游戏
Luogu LOJ 分析 首先你需要看懂这篇题解。 设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。 ...
洛谷4548 [CTSC2006]歌唱王国
Luogu 分析 以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。 设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。 分析一下可以列出这样一个式子 用 KMP / has...
洛谷3343 [ZJOI2015]地震后的幻想乡
Luogu LOJ 分析 首先看到题目里的提示： 对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\cdots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 。 考虑一个暴力做法：枚举边权的相对大小，然后 Kruskal 求最小生成树并用这个提示算答案。 进一步考虑这样的一个做法：钦定一个边集 $S$ 作为前 $|S|$ 小的边，如果这个...