还差很多
# 题面
有一个长度为 $n$ 的数列 $\{a_1,a_2,\dots,a_n\}$ 和一个整数 $b$,初始 $a_i=0,b=0$,$a_i$ 值域为 $[0,m-1]$。进行 $Q$ 次操作,每次操作是下列所有操作中的一种:
A l r v
:对 $i\in[l,r]$,$a_i\leftarrow\max\{a_i,v\}$,这种操作一共包含 $m\times \frac{n(n+1)}{2}$ 种;B l r v
:对 $i\in[l,r]$,$a_i\leftarrow\min\{a_i,v\}$,这种操作一共包含 $m\times \frac{n(n+1)}{2}$ 种;C l r
:$b\leftarrow b+\sum_{i=l}^ra_i$,这种操作一共包含 $\frac{n(n+1)}2$ 种。
求 $Q$ 次操作后 $b$ 的期望(原题是求所有方案的 $b$ 之和,本质一样……)。
$1\le n,m,Q\le2\times 10^5$
# 解析
这是一道利用期望线性性分拆贡献的好题:),具体分拆贡献分为两步:
(Ⅰ)将 $\mathbf{E(b)}$ 分拆为每一次操作对 $\mathbf b$ 的贡献。
由题意易知只有 C操作 会对 $b$ 有贡献。若第 $i$ 次操作是 C 操作,设其对 $b$ 的贡献为 $ans_i$。一共有 $(2m+1)\binom n2$ 种操作,而 C 操作有 $\binom n2$ 种,于是某一次操作是 C 操作的概率是 $\frac 1{2m+1}$。然后可以写出下面的式子:
考虑怎么计算 $E(ans_j)$。
Tab. 记 $a_{i,j}$ 表示数字 $a_i$ 在 $j$ 次操作后的值。
(Ⅱ)将 $\mathbf{E(ans_j)}$ 分拆为每个 $\mathbf{E(a_{i,j})}$ 的贡献。
某次操作区间包含 $a_i$ 的概率为 $\frac{i(n-i+1)}{\binom n2}$,则
而对于 $E(a_{i,j})$,要利用到将离散期望用概率表达的技巧:
为了方便计算上式的概率,我们定义一次操作对 $a_i$ 有效,当且仅当:
- 是 A/B 操作;
- 操作区间包含 $i$;
- 如果是 A(max) 操作,则要求 $v\ge a_i$;如果是 B(min) 操作,则要求 $v< a_i$。
那么可以推得某一次操作对 $a_i$ 有效的概率为 $H_i=\frac{i(n-i+1)}{\binom n2}\cdot\frac{2m}{2m+1}\cdot\frac{a_i+(m-a_i-1)}{m}$,发现概率与 $a_i$ 无关。
那么什么时候会有 $a_{i,j}>k$?当且仅当最后一次有效操作的 $v$ 有 $v>k$。所以 $P(a_{i,j}>k)$ 可以这样计算:
- 在前 $(j-1)$ 次操作中(第 $j$ 次是 C 操作,一定无效)存在有效操作:$[1-(1-H_i)^{j-1}]$(即从所有方案中减去 $j-1$ 次操作都无效的方案);
- 最后一次有效操作 $v>k$:$\frac{m-k-1}m$。
所以 $P(a_{i,j}>k)=\frac{m-k-1}m[1-(1-H_i)^{j-1}]$
综上
最后
后面对 $1-(1-H_i)^{j-1}$ 的式子求和就用等比数列,可以做到 $O(\log Q)$,于是总复杂度 $O(n\log Q)$。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
Linked 何日重到苏澜桥-Bilibili