做题笔记 - 概率论

Wandering Robots(ICPC 2017 Shenyang)

镜像赛场上没切出来的人均题之一。

设在 $(x,y)$ 停留的概率为 $f_{x,y}$，$(x,y)$ 可以通往的相邻点有有 $d_{x,y}$ 个，那么显然有 $f_{x,y}=\frac{f_{x,y}}{d_{x,y}+1}+\frac{f_{x-1,y}}{d_{x-1,y}+1}+\frac{f_{x+1,y}}{d_{x+1,y}+1}+\frac{f_{x,y-1}}{d_{x,y-1}+1}+\frac{f_{x,y+1}}{d_{x,y+1}+1}$。然后还注意到 $\sum f_{x,y}=1$，所以可以联立一个概率方程组，解这个方程组就行。

然后观察样例，会发现一个很有趣的结论，概率即为目标点集的出度和/总点集的出度和。有些佬用这个方法写出来了但是不会证，但是你会发现，只要满足上面的概率方程组就行了，而这是易证的。

然后会发现相对于正常的图而言，被截掉的出度只与 $k$ 有关，所以我们暴力找到这些点，去重一下就可以算出实际出度了。

聚魔石(19th 华中地区邀请赛)

区间 dp+期望板子。

最开始看错数据范围，以为平方复杂度过不去，然后思考了半小时未果，发现看错数据范围了。

期望题目倒过来做，如果正着做还要同时算概率很麻烦。设 $f_{l,r}$ 为区间 $[l,r]$ 向外扩展之后发生共鸣的期望次数。转移显然有：

$$f_{l,r}=\frac{w_{l-1}}{w_{l-1}+w_r}\cdot(f_{l-1,r}+[p_{l-1}\gt\max_{i\in[l,r]}p_i])+\frac{w_{r+1}}{w_l+w_{r+1}}\cdot(f_{l,r+1}+[p_{r+1}\gt\max_{i\in[l,r]}p_i])$$

。注意 $[s,s]$ 的贡献也是 $1$。

Random Walk Distance

来源：AT_abc463_g

难度：2452

oonp 怎么还有这种题的。

这是一个组合数前缀和状物。单独处理每次询问需要 $\Theta(n)$。考虑能不能将所有询问混起来做。

考虑单独处理的时候是怎么样的。先扔掉期望，这实际上是 $i$ 号点站了 $\binom{n}{i}$ 个人，然后问所有人到某一个点的距离之和。单独处理的一种做法是从最左端开始移动 $x$，记录当前答案和左右两边各站了多少人。一开始左边没人，右边站了 $2^n$。跨越 $i$ 号点，就要将左右两边站的人数和答案做一次系数为 $\binom{n}{i}$ 的更新。预处理组合数可以简单解决。

现在的问题是要把所有询问整合处理。我们在移动的时候只关照了 $x$ 维度，对于 $n$ 维度目前似乎是没有办法。考虑 $n$ 变到 $n+1$ 的过程，实际上是每一个点的人有丝分裂成人数相同的两拨人分别往左右移了一个。对于远离 $x$ 的点，两拨人左右各移动一格抵消贡献了，实际上贡献恰好翻倍了。如果 $x$ 作为上一轮的点，设当前有 $\binom{n}{i}$ 个人，则贡献为翻倍和 $2\binom{n}{i}$，因为有两拨 $\binom{n}{i}$ 的人从这个点离开走了一步 $\binom{n}{i}$；左边和右边的人都同时翻倍且加上了 $\binom{n}{i}$。如果 $x$ 作为下一轮的点，设左边有 $\binom{n}{j}$ 个人，右边有 $\binom{n}{j+1}$，则贡献仅有翻倍，左边和右边的人都同时翻倍且各减去 $\binom{n}{j}$ 和 $\binom{n}{j+1}$。这不难理解。对于 $n$ 变到 $n-1$ 同理。也就是，我们实际上可以通过维护左边、右边的人数和当前答案去做到变化 $n$ 的复杂度是线性的。

那么更改 $x$ 和 $n$ 移动 $1$ 的复杂度是 $\Theta(1)$ 的。发现这不就是莫队吗。然后莫队直接上。时间复杂度 $\Theta(N\sqrt{N})(N=2\times10^5)$。注意这篇题解为了方便理解把期望扔掉了，实际写代码的时候需要加上期望系数。