不常用的技巧：期望解和式
xzz_cat6
·
·
算法·理论
思想
众所周知，期望乘方案数即为总和。于是如果遇到了一个和式，并且非常难算，但是可以快速求出期望和总方案数，即可求出和式。
例题 1
求出下式的通项公式：
\sum_{i=1}^n \sum_{j=1}^{n} i\times j
法 1
\sum_{i=1}^n \sum_{j=1}^{n} i\times j\\
=\sum_{i=1}^n i\times \sum_{j=1}^{n} j\\
=(\sum_{i=1}^n i)^2\\
=(\frac{n\times(n+1)}{2})^2\\
=\frac{n^2\times (n+1)^2}{2}
法 2（重点）
$i\times j$ 的期望：$i$ 与 $j$ 在 1 到 $n$ 之间等概率随机，于是有下式:
$$
E(i\times j)\\
=E(i)\times E(j)\\
=(\frac{n+1}{2})^2
$$
将方案数与期望相乘，与方法 1 的结果相等。
# 例题 2
求出下式的所有可能值的和：
$$
\sum_{i-1}^n \sum_{j=i+1}^n \left \lfloor \frac{a_i + a_j}{2} \right \rfloor
$$
其中 $\forall a_i \in [1,m]$。
## 题解
取整是不能求期望的，于是把原式化简一下，变成
$$\sum \frac{a_i + a_j - (a_i+a_j ) \bmod 2}{2}$$
对其求期望，已知
$$E(a\times P)=a\times E(P)$$
记作式一。
$$E(P_1+P_2)=E(P_1)+E(P_2)$$
记作式二。
根据式一，原式的期望变成
$$E(\frac{a_i + a_j - (a_i+a_j ) \bmod 2}{2})\times \frac{(n+1)\times n}{2}$$
根据式二，原式的期望变为
$$\frac{1}{2}\times\frac{(n+1)\times n}{2}\times E(a_i + a_j - (a_i+a_j ) \bmod 2)$$
根据式一，原式的期望变为
$$\frac{1}{2}\times\frac{(n+1)\times n}{2}\times (E(a_i) + E(a_j) - E((a_i+a_j ) \bmod 2))$$
又因为
$$E(a_i) + E(a_j)=1+m\\
E((a_i+a_j ) \bmod 2)=\frac{2}{\binom{1}{\left \lfloor (m+1)\div 2 \right \rfloor }\binom {1}{ \left \lfloor m\div2 \right \rfloor }}$$
于是原式的期望化为：
$$
\frac{(n+1)\times n}{4}\times (1+m -\frac{2}{\binom {1}{\left \lfloor (m+1)\div 2 \right \rfloor }\times \binom{1}{\left \lfloor m\div 2 \right \rfloor }} )
$$
最后再乘上一个总方案数，即为 $m^n$，答案就可以 $O(\log n)$ 算出来了。
# 习题
[P4562](https://www.luogu.com.cn/problem/P4562)
## 题意
给一个区间 $[l,r]$，每次选一个数，把它和它的倍数去掉，耗时为 $[l,r]$ 的所有数都被消掉的次数，问所以不同选则方式的总耗时。
## 题解
参考[这篇文章](https://www.luogu.com.cn/article/5s9z0xx9)。
我们经过观察发现，对于每个数字，我们可以分成关键数字和非关键数字，关键数字为在这 $[l,r]$ 里面没有数字（除他本身）的倍数是它。显而易见的是对于一个排列最末尾的关键数字所在的位置即是它的检查时间。问题转换为在 $n$ 个数中随机取 $k$ 个数，最末尾的数字的位置的期望乘以 $n$ 的阶乘（即所有排列总数）。显然如果是期望，那么肯定是平均分布,可以得出位置的期望为 $$\frac{k}{k+1}×(n+1)$$ (因为位置从1开始数起)，则总答案即为
$$\frac{k}{k+1} \times (n+1)!$$