发布于 ,更新于 

概率杂题

P4562 [JXOI2018]游戏

给定区间 \([l,r]\),每次选择一个未选择过的数,将这个数以及它的所有倍数标记,每一种方案全部标记所用次数记为 \(t\),求所有可能 \(t\) 的和。

首先想到每次将所有点标记的实质,就是将 \(\left[l,r\right]\)没有此区间内非自身的因数的数标记完。称这样的数为关键数,设关键数有 \(k\) 个,则实际上标记次数就是最后一个关键数的位置。

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

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

于是,最后一个点的位置的期望,即 \(t\) 的期望为下式

\[ \begin{aligned} &\ \ \ \ \ n-\cfrac{n-k}{k+1} \newline &= \cfrac{nk+n-n+k}{k+1} \newline &= \cfrac{(n+1)k}{k+1} \end{aligned} \]

求所有可能的 \(t\) 的值的和,乘一个阶乘就好了。

\[ \begin{aligned} &\ \ \ \ \ \cfrac{(n+1)k}{k+1}n! \newline &= \cfrac{k}{k+1}(n+1)! \end{aligned} \]

取模的话,求完阶乘 \(\times k\) 再乘个 逆元 就行了。

P4284 [SHOI2014] 概率充电器

给定一棵树,每条边能导电的概率为 \(p_i\),每个点自己带电的概率为 \(q_i\),求带电点个数的期望。

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

考虑单个点有电的情况:

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

\(f_u\) 为点 \(u\) 带电的期望:

  • 第一种情况的概率就是 \(q_u\),所以直接 \(f_u = q_u\) 就行。
  • 第二种情况非常像树形 DP 的样子,容易想到从叶子节点向上推就行。
    • 考虑两个独立事件发生其中一件即可的概率: \(P(A+B)=P(A)+(1-P(A))P(B)\),即 \(A\) 事件的概率 \(+\) \((B\) 事件 \(+\) \(A\) 事件未发生 \()\) 的概率。
    • 进行 dfs,回溯的时候统计:
      • 设当前点为 \(u\),儿子为 \(v\),则有 \(f_u = f_u + (1-f_u)p_{u,v}f_v\)
  • 第三种情况实际上也是树形 DP,只不过变成了正推,从 \(u\) 计算对 \(v\) 的贡献。
    • 假设当前到达 \(u\),且 \(f_u\) 已经算好了,考虑如何把贡献传给 \(f_v\)
    • 容易想到 \(u\) 能贡献给 \(v\) 电流的那部分概率,实际上是 \(f_u\) 扔掉 \(v\) 这棵子树的部分。
    • 换句话说,贡献 \(=\) \(u\) 有电的概率 \(-\) \(u\) 不考虑 \(v\) 的有电的概率,再乘边的概率之类的常数即可。
    • \(\langle u,v \rangle=e\)\(u\) 不考虑 \(v\) 的有电的概率为 \(g_u\)\(v\) 只考虑下方来电有电的概率为 \(l_v\),有柿子: \[ \begin{aligned} f_u &= g_u + l_vp_e(1-g_u) \newline f_u &= g_u + l_vp_e-l_vp_eg_u \newline f_u - l_vp_e &= g_u(1-l_vp_e) \newline g_u &= \cfrac {f_u-l_vp_e}{1-l_vp_e} \newline f_u - g_u &= f_u - \cfrac {f_u-l_vp_e}{1-l_vp_e} \end{aligned} \]
    • 考虑完 \(u\) 有电的贡献,乘一下边的概率和 \(v\) 没电的概率就行了 \[ f_v = f_v + (1-f_v)\cdot p_e \cdot(f_u - \cfrac {f_u-l_vp_e}{1-l_vp_e}) \]

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

SPOJ 4060 KPGAME

传送门

CF 1316 F

又是一个重量级题目。

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

好,接下来考虑一个点对对期望的贡献。
假设有点对 \(a_i,a_j,i<j\),显然权值的贡献是 \(a_ia_j\)
然后来看概率,由于是相邻的,所以能随便挑选的只有 \(i\) 左边,\(j\) 右边的点,总共有 \((i-1)+(m-j)\) 个,满足两个点相邻的子序列数量即为 \(2^{(i-1)+(m-j)}\),而子序列的总数有 \(2^n\) 个。因此,这两个点相邻的概率为:

\[ \frac {2^{(i-1)+(m-j)}}{2^n} = \frac {1}{2^{n-i+1-j-n}} = \frac 1{2^{j-i+1}} \]

于是得出点对 \(a_i,a_j,i<j\) 对期望的贡献:\(\frac {a_ia_j}{2^{j-i+1}}\)

然后给定一个数列,其权值的期望直接枚举点对计算就是答案:\(\sum_{i=1}^n \sum_{j=i+1}^n \frac {a_ia_j}{2^{j-i+1}}\)

但是这玩意带单点修改,直接用这个式子的话就是一个非常优秀的 \(\Theta(qn^2)\) 的做法。

单点修改。考虑分治。

把一个序列分成两段:\([1,m],[m+1,n]\),那它的贡献可以分成三部分:

  • \([1,m]\) 的贡献
  • \([m+1,n]\) 的贡献
  • 跨越两个区间的点对的贡献

前两个可以分治解决,问题在于第三个东西。
首先这个东西的式子是很好写的:\(\sum_{i=1}^m \sum_{j=m+1}^n \frac {a_ia_j}{2^{j-i+1}}\)
为了分治,我们得把这个式子拆成左右两半。欸,这 \(1\sim m\)\(m+1\sim n\) 根本就没交集,那就直接拆开就好了!

\[ \begin{aligned} &\ \ \ \ \ \sum_{i=1}^m \sum_{j=m+1}^n \frac {a_ia_j}{2^{j-i+1}} \newline &= \sum_{i=1}^m \sum_{j=m+1}^n \frac {a_ia_j}{2^{j-m+m-i+1}} \newline &= (\sum_{i=1}^m \frac {a_i}{2^{m-i+1}})(\sum_{j=m+1}^n \frac {a_j}{2^{j-m}}) \end{aligned} \]

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

设一个区间的答案为 \(f\),上面拆成的两个部分一个是 \(ls\) 一个是 \(rs\)\(len(x,y) = y-x+1\) 表示一个区间的长度。

对于一个区间 \([l,r]\),有如下一堆东西:

\[ \begin{cases} f(i,i) = 0 \newline ls(i,i) = rs(i,i) = 1 \newline f(l,r) = f(l,m) + f(m+1,r) + ls(l,m)rs(m+1,r)\newline ls(l,r) = ls(l,m) + \frac {rs(m+1,r)}{2^{len(l,m)}} \newline rs(l,r) = rs(m+1,r) + \frac {rs(l,m)}{2^{len(m+1,r)}} \end{cases} \]

最终答案是 \(f(1,n)\)

这样的分治,最终复杂度是 \(\Theta(qn)\) 的,还是不够。

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

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

push_up 就用上面的式子就好。

这样的做法时间复杂度为 \(\Theta(n+q\log n)\),非常能过。

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