概率杂题

P4562 [JXOI2018]游戏

给定区间 $[𝑙, 𝑟]$ ，每次选择一个未选择过的数，将这个数以及它的所有倍数标记，每一种方案全部标记所用次数记为 $𝑡$ ，求所有可能 $𝑡$ 的和。

首先想到每次将所有点标记的实质，就是将 $[𝑙, 𝑟]$ 中没有在此区间内的非自身的因数的数标记完。称这样的数为关键数，设关键数有 $𝑘$ 个，则实际上标记次数就是最后一个关键数的位置。

最后一个关键数的位置...不沾头不沾尾，所以换个方向考虑——最后一个关键数的位置可以替换为它后面的非关键数的数量。

实际上， $𝑘$ 个关键数把整个区间分成了 $𝑘 + 1$ 份。设区间长度为 $1$ ，则一个非关键数在最后一段区间上的期望就是 $1 𝑘 + 1$ （ $𝑘 + 1$ 种情况，每种情况都在段区间上，只有一种情况在目标区间上）， $𝑛 - 𝑘$ 个非关键点在最后一段区间上的期望就是 $𝑛 - 𝑘 𝑘 + 1$ 。（注意这里概率到期望的转换，要想想为什么期望成了求解目标）

于是，最后一个点的位置的期望，即 $𝑡$ 的期望为下式

$𝑛 - 𝑛 - 𝑘 𝑘 + 1 = 𝑛 𝑘 + 𝑛 - 𝑛 + 𝑘 𝑘 + 1 = (𝑛 + 1) 𝑘 𝑘 + 1$

求所有可能的 $𝑡$ 的值的和，乘一个阶乘就好了。

$(𝑛 + 1) 𝑘 𝑘 + 1 𝑛! = 𝑘 𝑘 + 1 (𝑛 + 1)!$

取模的话，求完阶乘 $\times 𝑘$ 再乘个逆元就行了。

P4284 [SHOI2014] 概率充电器

给定一棵树，每条边能导电的概率为 $𝑝 𝑖$ ，每个点自己带电的概率为 $𝑞 𝑖$ ，求带电点个数的期望。

根据期望的线性性，考虑求每个点有电的期望。因为只有 $0, 1$ 两种情况，因此求概率就行了。

考虑单个点有电的情况：

自己有电
儿子有电，和儿子连边导电
父亲有电，和父亲连边导电

设 $𝑓 𝑢$ 为点 $𝑢$ 带电的期望：

第一种情况的概率就是 $𝑞 𝑢$ ，所以直接 $𝑓 𝑢 = 𝑞 𝑢$ 就行。
第二种情况非常像树形 DP 的样子，容易想到从叶子节点向上推就行。
- 考虑两个独立事件发生其中一件即可的概率： $𝑃 (𝐴 + 𝐵) = 𝑃 (𝐴) + (1 - 𝑃 (𝐴)) 𝑃 (𝐵)$ ，即 $𝐴$ 事件的概率 $+$ $(𝐵$ 事件 $+$ $𝐴$ 事件未发生 $)$ 的概率。
- 进行 dfs，回溯的时候统计：
  - 设当前点为 $𝑢$ ，儿子为 $𝑣$ ，则有 $𝑓 𝑢 = 𝑓 𝑢 + (1 - 𝑓 𝑢) 𝑝 𝑢, 𝑣 𝑓 𝑣$
第三种情况实际上也是树形 DP，只不过变成了正推，从 $𝑢$ 计算对 $𝑣$ 的贡献。
- 假设当前到达 $𝑢$ ，且 $𝑓 𝑢$ 已经算好了，考虑如何把贡献传给 $𝑓 𝑣$ 。
- 容易想到 $𝑢$ 能贡献给 $𝑣$ 电流的那部分概率，实际上是 $𝑓 𝑢$ 扔掉 $𝑣$ 这棵子树的部分。
- 换句话说，贡献 $=$ $𝑢$ 有电的概率 $-$ $𝑢$ 不考虑 $𝑣$ 的有电的概率，再乘边的概率之类的常数即可。
- 设 $⟨ 𝑢, 𝑣 ⟩ = 𝑒$ ， $𝑢$ 不考虑 $𝑣$ 的有电的概率为 $𝑔 𝑢$ ， $𝑣$ 只考虑下方来电有电的概率为 $𝑙 𝑣$ ，有柿子： $𝑓 𝑢 = 𝑔 𝑢 + 𝑙 𝑣 𝑝 𝑒 (1 - 𝑔 𝑢) 𝑓 𝑢 = 𝑔 𝑢 + 𝑙 𝑣 𝑝 𝑒 - 𝑙 𝑣 𝑝 𝑒 𝑔 𝑢 𝑓 𝑢 - 𝑙 𝑣 𝑝 𝑒 = 𝑔 𝑢 (1 - 𝑙 𝑣 𝑝 𝑒) 𝑔 𝑢 = 𝑓 𝑢 - 𝑙 𝑣 𝑝 𝑒 1 - 𝑙 𝑣 𝑝 𝑒 𝑓 𝑢 - 𝑔 𝑢 = 𝑓 𝑢 - 𝑓 𝑢 - 𝑙 𝑣 𝑝 𝑒 1 - 𝑙 𝑣 𝑝 𝑒$
- 考虑完 $𝑢$ 有电的贡献，乘一下边的概率和 $𝑣$ 没电的概率就行了 $𝑓 𝑣 = 𝑓 𝑣 + (1 - 𝑓 𝑣) \cdot 𝑝 𝑒 \cdot (𝑓 𝑢 - 𝑓 𝑢 - 𝑙 𝑣 𝑝 𝑒 1 - 𝑙 𝑣 𝑝 𝑒)$

柿子推完了，写两个 dfs 算答案即可。

SPOJ 4060 KPGAME

传送门

CF 1316 F

又是一个重量级题目。

首先我们发现他这个数列是假的，因为求权值的时候是“排序”后再求，子序列也不需要连续，所以我们直接把它当一个数的集合做，不需要维护他们在原数列中的顺序。下面所说的下标都是排序后的下标。

好，接下来考虑一个点对对期望的贡献。
假设有点对 $𝑎 𝑖, 𝑎 𝑗, 𝑖 < 𝑗$ ，显然权值的贡献是 $𝑎 𝑖 𝑎 𝑗$ 。
然后来看概率，由于是相邻的，所以能随便挑选的只有 $𝑖$ 左边， $𝑗$ 右边的点，总共有 $(𝑖 - 1) + (𝑚 - 𝑗)$ 个，满足两个点相邻的子序列数量即为 $2 (𝑖 - 1) + (𝑚 - 𝑗)$ ，而子序列的总数有 $2 𝑛$ 个。因此，这两个点相邻的概率为：

$2 (𝑖 - 1) + (𝑚 - 𝑗) 2 𝑛 = 1 2 𝑛 - 𝑖 + 1 - 𝑗 - 𝑛 = 1 2 𝑗 - 𝑖 + 1$

于是得出点对 $𝑎 𝑖, 𝑎 𝑗, 𝑖 < 𝑗$ 对期望的贡献： $𝑎 𝑖 𝑎 𝑗 2 𝑗 - 𝑖 + 1$ 。

然后给定一个数列，其权值的期望直接枚举点对计算就是答案： $\sum 𝑛 𝑖 = 1 \sum 𝑛 𝑗 = 𝑖 + 1 𝑎 𝑖 𝑎 𝑗 2 𝑗 - 𝑖 + 1$ 。

但是这玩意带单点修改，直接用这个式子的话就是一个非常优秀的 $Θ (𝑞 𝑛 2)$ 的做法。

单点修改。考虑分治。

把一个序列分成两段： $[1, 𝑚], [𝑚 + 1, 𝑛]$ ，那它的贡献可以分成三部分：

$[1, 𝑚]$ 的贡献
$[𝑚 + 1, 𝑛]$ 的贡献
跨越两个区间的点对的贡献

前两个可以分治解决，问题在于第三个东西。
首先这个东西的式子是很好写的： $\sum 𝑚 𝑖 = 1 \sum 𝑛 𝑗 = 𝑚 + 1 𝑎 𝑖 𝑎 𝑗 2 𝑗 - 𝑖 + 1$
为了分治，我们得把这个式子拆成左右两半。欸，这 $1 \sim 𝑚$ 和 $𝑚 + 1 \sim 𝑛$ 根本就没交集，那就直接拆开就好了！

$𝑚 \sum 𝑖 = 1 𝑛 \sum 𝑗 = 𝑚 + 1 𝑎 𝑖 𝑎 𝑗 2 𝑗 - 𝑖 + 1 = 𝑚 \sum 𝑖 = 1 𝑛 \sum 𝑗 = 𝑚 + 1 𝑎 𝑖 𝑎 𝑗 2 𝑗 - 𝑚 + 𝑚 - 𝑖 + 1 = (𝑚 \sum 𝑖 = 1 𝑎 𝑖 2 𝑚 - 𝑖 + 1) (𝑛 \sum 𝑗 = 𝑚 + 1 𝑎 𝑗 2 𝑗 - 𝑚)$

然后我们就可以直接分治解决了。

设一个区间的答案为 $𝑓$ ，上面拆成的两个部分一个是 $𝑙 𝑠$ 一个是 $𝑟 𝑠$ ， $𝑙 𝑒 𝑛 (𝑥, 𝑦) = 𝑦 - 𝑥 + 1$ 表示一个区间的长度。

对于一个区间 $[𝑙, 𝑟]$ ，有如下一堆东西：

$⎧ {⎨ {⎩ 𝑓 (𝑖, 𝑖) = 0 𝑙 𝑠 (𝑖, 𝑖) = 𝑟 𝑠 (𝑖, 𝑖) = 1 𝑓 (𝑙, 𝑟) = 𝑓 (𝑙, 𝑚) + 𝑓 (𝑚 + 1, 𝑟) + 𝑙 𝑠 (𝑙, 𝑚) 𝑟 𝑠 (𝑚 + 1, 𝑟) 𝑙 𝑠 (𝑙, 𝑟) = 𝑙 𝑠 (𝑙, 𝑚) + 𝑟 𝑠 (𝑚 + 1, 𝑟) 2 𝑙 𝑒 𝑛 (𝑙, 𝑚) 𝑟 𝑠 (𝑙, 𝑟) = 𝑟 𝑠 (𝑚 + 1, 𝑟) + 𝑟 𝑠 (𝑙, 𝑚) 2 𝑙 𝑒 𝑛 (𝑚 + 1, 𝑟)$

最终答案是 $𝑓 (1, 𝑛)$ 。

这样的分治，最终复杂度是 $Θ (𝑞 𝑛)$ 的，还是不够。

这个分治实际上很容易用线段树维护，但是修改权值怎么办？答案是使用权值线段树。

我们将询问离线下来，把原数列和询问中的数字全部离散化，然后存到权值线段树里面,这样显然就把排序的部分做完了。
然后对于每个线段树节点，维护当前区间里面的有效点个数，以及上面那一堆东西，但是 $𝑙 𝑒 𝑛$ 就可以替换成刚才提到的点数了。

push_up 就用上面的式子就好。

这样的做法时间复杂度为 $Θ (𝑛 + 𝑞 l o g 𝑛)$ ，非常能过。

但是另一个细节的点来了：离散化。由于两个相同的数作为点对也会产生贡献，所以在离散化的时候给他们分配不同的编号。

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。