概率杂题

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)\)，非常能过。

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