「算法学习」期望与概率

算法学习($\times$)

算法复习($\times$)

我在学啥($\sqrt{}$)

概率与期望 (n 次 放 送)

概念:pause

Part 1 高斯消元

解方程,一般适用于随机游走一类的问题。

图上随机游走:

  • $f[u] = \sum p[u][v]*(f[v]+w[u][v])$
  • 如果是 DAG 则按 topo 序 DP, 否则将 n^3 消元

概率 :计算期望在这个节点上,停留多少步。

  • $ f[u] = \sum p[v][u]f[v] + (u=s)$
  • 如果起点在 i 号点的概率为 $q_i$ ,则把等式的后半部分改为 $q_i$

HNOI 2013 游走

给定一张图,从 1 到 n,随机游走,求每一条边期望被经过次数, $ n\le 500$ 。

转为算每个点的期望,每一条边的期望就是起点的期望乘上起点的出度

SDOI 2012 走迷宫

有 $n$ 个点 $m$ 条边的有向图,求 $s$ 到 $t$ 的期望步数,$n \le 10^4,每个 SCC \le 100$

缩点之后对于每个 SCC 暴搞消元,然后变成一个 DAG 。

Band Matrix 带状矩阵

一个点的转移只和自己左右的 $d$ 项有关,消元矩阵除了对角的 $O(d)$ 行别的东西都是 0 。

考虑高斯消元的过程,因为是带状矩阵,所以每次我们消元的时候只需要往下消 d 行的 d 列,复杂度 $O(nd^2)$。

我们再考虑换主元的过程,如果我们把下边的某一行换上来再消元,矩阵的心态可能会发生改变,不符合带状的性质,于是我们改成把右边的某一列换过来消元,依然可以满足带状矩阵的性质。

Snipaste_2019-12-13_09-01-55

例题

  • WF 2014 H
  • 网格图的生成树 :Matrix Tree 定理,由于矩阵是稀疏图所以复杂度是 $O(nm^3)$
  • CF 475 E

主元法 (代入消元法)

wxh 2019 集训队论文

  • 小学生例题:$n * m$ 的网格,每个开关控制包括自己的周围 5 格,求最少多少步把所有灯都熄灭。($n \le 20, m \le 10^4 $)
    1. 枚举第一列开关的状态,然后可以 $O(nm)$ 推出每个开关的状态,判断合法性。
    2. 我们设变量 $x_1,x_2\cdots x_n$ 表示第一列的开关的状态,然后每个位置都可以被表示成这 $n$ 个状态中的若干个变量的异或和,一直推到最后一列,然后枚举第一例开关的状态可以直接得到最后一列的状态,复杂度 $O(nm + 2^nn)$

例题

  • TorusSailing

    废 物 利 用 再 放 送

    我们设 $f_{x,y}$ 为从 $(x,y)$ 走到 $(n,m)$ 的期望步数,设最后一行和最后一列的 $f$ 值为变量,别的位置可以用他们表示出来,最后消元,注意唯一的细节是 $f_{n,m}$ 的格点的期望是 0 ,否则会解出超解。

  • CF 475 E

    用黄点来建方程,消元

    具体方法就是我们观察最左边的一个黄点,它的转移只和它右边的那个蓝点有关,我们可以列出关于他的转移方程,然后经过移项和换元,可以得到蓝点关于黄点的方程。

    Snipaste_2019-12-13_09-31-27

  • 集训队互测 day5 国际象棋

    差不大多,由于棋子走的是马子步,所以设元的时候可能要设两行两列

一般的解方程优化就是上面两种,带状网格适用于行列式解方程,而主元法只能用于网格图。

当然稀疏矩阵的消元还有一种 BM 算法,但是不会,复杂度 $O(ne)$ ,n 是变量总个数, m 是非 0 项个数,一般适用于平面图。全称:$Berlekamp-Massey $

毛爷爷 2017 论文

钟子谦 2019 论文

  • Fox Rocks(FHC)

    Snipaste_2019-12-13_09-52-39

    观察图的性质,我们发现每 4 个点会形成一个块,然后对于一个询问,我们先求出 x 到 y 所在的块的那 4 个点的概率, 然后对于 x 这个点 和 y 块内的点以及我们新建的一个虚点(y这个块连出去的点)跑个消元就 vans 了。

    现在考虑修改,对于相邻两个块,我们计算出上一个块的每一个点第一次到这个块的每一个的点的概率,然后我们对每个图建一个线段树,上面的那个东西就可以比较轻松的求出来了。修改和合并的时候暴力 $4^3$ 搞就行了。都 是 常 数

概率生成函数 PGF

设随机变量 x 的概率生成函数为:

例题

  • 歌唱王国

    再 放 送

    $f_i$ 表示第一次匹配玩模式串时长度为 i 的的概率,$g_i$ 表示长度为 i 时还未结束的概率,F 和 G 是他们的概率生成函数,设我们想要的字符串长度为 $L$, 推理一番我们可以写出两个恒等式。

    第一个式子的含义即长度为 x 的未结束的串往后加一个字符可能结束也可能不结束($g(x )=f(x+1)+g(x+1)$)。

第二个式子的含义是我们往一个未结束的状态后面直接假如一整个我们想要的字符串,必然会转移到结束的状态,但是对于我们要的字符串的一个长度为 len 的 border ,假设当前生成的这个未结束的串匹配了模式串的前 L - len 位,那么我们只需加入这个 border (也就是后 len 位),那么它就提早结束了。

对于 1 式,我们把两边同时求导,并且把 x = 1 带入,可得:

也就是我们求出了$G(1)$,也就求出了答案。

对于 2 式,我们把 1 带入,并在两边同时乘上 $m^L$ ,得:

又因为 $F(1) = 1$ (所有概率加在一起就是 1),所以有:

还有一些亦可赛艇的东西,因为我们拥有了两个式子,我一我们可以直接把 $F(x)$ 等于什么给解出来。

思考

  • 优点:处理简洁,易扩展,可以改成求方差,或者求某一项的值。
  • 缺点:列方程比较不直观,需要一定的套路积累和练习。

期望线性性

  • $E(x + y) = E(x) + E(y)$
  1. 在 $1\cdots m$ 的序列中随机选一个数,选 n 次,最大数的期望。

  2. 在 $1\cdots m$ 的序列中随机选 $n$ 个数,最大数的期望

  3. 在长度为 $n$ 的序列 $\{a\}$ 中随机选出一个集合,求 $E(\max a_i-\min a_i)$

    拆开做,用 2 的做法。

  4. 给一个多边形,选一个点集围成一个新的多边形,求新的多边形的周长期望。

    转化为求每一条边在新多边形中出现的期望。

    原题 $n = 10^5$,但是要求输出 double ,于是对于太远的两个点,我们求没有必要计算他们的贡献了,因为太小了。

  5. 网格图上条件如上,求多边形内部整点个数

    通过 pick’s theorem 转化成计算每条边的贡献,面积用差积搞一下。

    由于 double 精度依然只用计算比较近的点对。

  6. 有一个序列,每一随机去掉序列的一端,求最后一个数的期望。

  7. CF 280 C

    给定一棵树,每次砍掉一个子树,求整棵树被砍完的期望。

    考虑将模型做一个转换,变成我们随机一个节点的排列,在这个序列中如果一个点出现在它的所有祖先之前才会产生贡献,于是答案就是:

CF1153 F

考虑把贡献拆开,对于每一个位置,我们算出它被覆盖 k 次的概率,最后积分回去。

CF235 D

首先要考虑如何转化,这道题肯定不能把贡献摊到每一个连通子图里,那么考虑把代价摊到图中的每个点,我们枚举一个要算贡献的点 u ,以及一个分治的点 v:

考虑树的 version ,u 会在 v 被删除是产生贡献必然有 v 和 u 依然联通,也就是 $u \to v$ 上没有电被删除,为 $\frac{1}{len_{u\to v}}$。

再考虑奇基环树的 version,假设从 u 到 v 的路径经过了环,则考虑容斥,一条路径联通 - 两条路径联通。

CF457 D

首先发现题目的代价其实等价于最终选中的行和列的子集总个数。

然后我们枚举一个行和列的子集,算出它出现的期望,最后加起来。

random

Snipaste_2019-12-13_14-06-22

考虑一个数 $i$ 会对答案产生怎么样的贡献,我们找到权值为 $i$ 的树,把这个序列 $\le i$ 的树标成 0,把这个序列 $>i$ 的数标位 1,然后大力状压转移。

考虑为什么这样转移之后概率分布依然是正确的,假设两个原序列中的逆序对,在我们生成的 01 序列中不是逆序对,那么我们在原序列中交换他们,在01 序列中没有影响,所以我们可以视为没有交换,所以概率依然是对的。

CTSC/BZOJ3148 没头脑与不高兴

先不考虑方差,只考虑期望怎么做。

依然是考虑一对数的贡献,我们枚举序列中的两个位置,如果他们都是 1,那么贡献为 0,如果他们都是 0,那么贡献为 0.5,

考虑一个 0 和一个 1 ,假设这个 1 是第 k 个,那么我们把所有 m 个 1 都拿出来,相当于这个 0 应该在序列的前 k 的位置才会产生贡献,所以贡献是 $\frac{k}{m+1}$,一个 1 和一个 0 的情况也差不多,是 $\frac{m + 1 - k}{m +1}$。

问题是如何处理修改,用线段树维护,首先可以很轻松的搞定一对 0 和一对 1 的情况,考虑这对数中既有 0 又有 1 的情况,假设对于某个 0 ,他前面有 k 个 1,而总共的 1 的个数是 m 个,我们可以推出这个 0 和前面的 1 的贡献为 $\frac{m+1-1}{m+1} +\frac{m+1-2}{m+1} +\cdots\frac{m+1-k}{m+1} = \frac{k(m+1)-\binom{k+1}{2}}{m+1}$ ,而反过来,一个 0 的后面有 k 个 1 的话,总贡献则是 $\frac{1}{m + 1}+\frac{2}{m+1} + \cdots + \frac{k}{m + 1} = \frac{\binom{k+1}2}{m + 1}$ ,所以我们要维护的也仅仅是 $\frac{k +1}{2}$ 而已,搞一搞就好了。

然后要求方差,怎么办呢,我们暴力搞出前几项,拉格朗日插值插一下就好了,具体是啥不知道。🕊

Projecteuler 584

题目可以转换为期望加入了多少个不合法的状态。

对于一个不合法的状态,会对答案产生一个 1 的贡献,也就是说我们把所有不合法状态产生的概率加在一起就是答案。

对于一个状态,假设在第 i 天出生的人数量为 $cnt_i$

考虑 dp, $f_{i,j,S}$ 表示前 $i$ 天,加入了 $j$ 个人,最近的 7 天过生日的人的状态,做完之后再求个和。

Projecteuler 522

首先对于每个叶子,都必须要有一个点连向它,需要一次修改修改,其次,对于一个孤立的环,我们要让它连出去,也要一次修改,经过如上操作后,我们的图中不存在连出去或者连进来的点了,所以操作次数就等于孤立环加叶子节点。

现在变成了我们算孤立的环和叶子的期望个数,叶子的期望个数显然是$\left(\frac{n-2}{n-1}\right)^{n-1} n$,环的期望是 $\sum_{k=2}^{n-1}\binom{n}{k}k(!\frac{1}{n-1})^k(\frac{n-1-k}{n-1})^{n-k}$ ,最后累加起来即可。

期望的平方/方差

Snipaste_2019-12-13_15-02-43

CF1236 F

考虑一个仙人掌森林,他的环数为 F,点数为 V,边数为 E,联通块个数为 G,则有

然后我们要算出这个东西的期望,还要算出这个东西的平方,至于平方这么做的话,暴力拆开暴力算:

Snipaste_2019-12-13_15-07-49

Snipaste_2019-12-13_15-09-11

CF 1187 F

首先不考虑方差,只考虑期望。

由于每两段之间存在一个端点,于是我们变成了求端点的期望,也就是求 $\sum_{i=1}^nP(a_i\ne a_{i+1})$,

拆开之后 $E(x_i)^2$ 比较好求,我们考虑如何求 $\sum_{i\ne j}E(i)E(j)$,对于 $|i - j| > 1$ ,他们相互独立,乘起来就好了,否则需要容斥一下。

Fibonacci’s Nightmare

直接照着定义去推就好了,考虑期望怎么算,显然有 $E(a_n)=\frac2n\sum_{i=0}^{n-1}E(a_i)$,找找规律照着推得到他就是 $n + 1$ 。

现在考虑怎么算平方的期望。

也是直接推就好了,后面要把求 $E(a_ia_j)$ 转化成递推去求。

Power of subtree

首先要把平方拆开,$x^n = S(n,i)\binom{x}{i}i!$。

我们令 $f_{i,j}$ 表示我们选择的 i 为根的子树,在里面选了 $j$ 个点,直接 DP 就好了。

火车题

依然是把 m 次方拆开,$x^m = \sum C_i\binom{x}{i}$,

设 $g_{i,j}$ 为 i 个点选 j 个联通块的方案数,推一推(大概是的吧¿)。

MinMax 容斥

杂题选讲

PKUWC2018 随机算法

直接做的话,$f_{S,T}$ 表示我们选了 $S$ ,独立集为 $T$ ,转移是 $O(n3^n)$,可能⑧大行。

考虑把这个算法修改一下,变成每次随机一个点,然后贪心的去把它加到独立集里去,易证他和原本策略一样,这样子我们 DP 就可以把 S 这一维去掉了。新的 DP 状态为 $f_{S,i}$ ,表示 现在考虑了点集 S ,独立集大小为 $i$ 的方案数,转移时枚举一个未被考虑过的点,显然如果这个点要被加到最大独立及里,那么和他相邻的数必须比他晚加入,并且加入后对答案没有影响,于是我们随便加入就好了, 具体的说,我们设 $w_k$ 为与点 $k$ 相邻的点的集合 (包括 $k$),那么转移的式子就是:

PKUWC2018 猎人杀

和上题一样,我们变成每次随机朝一个人开一枪,如果死了就再来一次直到开到活人为止,显然概率是一样的。

然后现在我们要求出在 1 号点死之后没有人活,发现不大好做,容斥一下变成在 1 号点之后 S 这个集合的人都还活着,概率是 $\sum_{i \geqslant 0}^{n-1-|S|}\left(1-p(s)-w_{1}\right)^{i} \cdot w_{1}$,然后容斥一下,,考虑计算某一个 $p(s)$ 的容斥系数,相当于是算

$\prod(1-x^{w_i})$ 次,因为 $\sum w_i \le 1e5$,所以分治 FFT 就好了。

一些结论

Snipaste_2019-12-13_16-04-01

方法1:对称性

线段覆盖再放送

Snipaste_2019-12-13_16-10-01

计算第 i 个点被覆盖了 i 次的概率可以用 DP,$f_{i,j}$ 表示考虑了前 i 个数,共有 j 条线段。

CF 303 E

新年的五维几何

枚举每个数的整数部分,然后每个数的小数部分都是随机分配的,也就是说每个数的小数部分大小排列也是等概率的。直接枚举排列,然后 check ,复杂度 $O(10^nn!n^2)$

AGC 020 Arcs on a Circle

这题不能爆枚每个弧的整数部分,所以就先爆枚实数部分。

方法2:积分

等车题

变成求某一个时刻还在等待的概率, 然后积分起来,$a_i$ 时刻还在等待的概率是 $\prod \frac{a_i-x}{a_i}$ ,积分之前要先把这个式子分治 FFT算出来。

Random Spanning Tree

Snipaste_2019-12-13_16-27-02

Snipaste_2019-12-13_16-30-46

第一问 : 枚举一个边权 x ,变为所有长度小于 x 的边加进去后图还是不连通的期望,不连通不好求,再转成边权小于 x 的所有边都加入后图联通的概率,暴搞一下,for一遍搞起来。

第二问:相当于对于第一问的每一条边加在一起。

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信