一道期望题
super蒟蒻
·
·
个人记录
https://47.119.140.90/studentCourse/class?groupId=218&courseId=135&contestId=6041#testTab=6042_2
给一个长度为 n 的数列 a。
每次等概率的选择一个 a_i>0 的 i，并令 a_i=a_i-1。
问期望多少次操作后 a_1 变成了 0，对 323232323 取模。
---------------------------
考虑计算每个 $i$ 被操作次数的期望。
因为 $i$ 能否操作只与 $1$ 有关，可以看成只有 $a_1,a_i$ 这两个数，然后算 $i$ 操作了多少次。
感性的理解话就是，选择操作别的位置，既不影响他们的状态，也不影响这个随机变量的值（因为算的是 $i$ 的期望操作次数）。
换句话说，不管你怎么操作别的地方，直到想要改变这两个数，它们的概率都是五五开的。
然后考虑设 $f_{x,y}$ 表示 $a_1=x,a_i=y$ 时，$i$ 的期望操作次数，有
$$f_{x,y}=\frac{f_{x-1,y}+f_{x,y-1}}{2}+\frac{1}{2}$$
边界是 $0$。
假设当前要算 $f_{n,m}$，考虑每个 $\frac{1}{2}$ 的贡献，有：
$$
\begin{aligned}
f_{n,m} &= \sum_{i=1}^{n}\sum_{j=1}^{m} (\frac{1}{2})^{n-i+m-j+1}\binom{n-i+m-j}{n-i} \\
&= \frac{1}{2}\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} (\frac{1}{2})^{i+j}\binom{i+j}{i}
\end{aligned}
$$
设 $c_x$ 表示 $x$ 在序列 $a$ 的出现次数（不包括$a_1$），那么：
$$ans = \sum_{i=1}^{max(\{a\})} c_i f_{a_1,i}$$
本来想写个 NTT 的，发现 323232323 这个模数不行。。。。
那就递推算，设 $d_m = f_{n,m+1}-f_{n,m}=\frac{1}{2}\sum_{i=0}^{n-1} (\frac{1}{2})^{i+m}\binom{i+m}{m}$。
$$
\begin{aligned}
2^{m+1}d_m &= \sum_{i=0}^{n-1} (\frac{1}{2})^i\binom{i+m}{m} \\
&= \sum_{i=0}^{n-1} (\frac{1}{2})^i\left [\binom{i+m-1}{m-1}+\binom{i+m-1}{m}\right ] \\
&= \sum_{i=0}^{n-1}(\frac{1}{2})^i\binom{i+m-1}{m-1}+\sum_{i=0}^{n-1}(\frac{1}{2})^i\binom{i+m-1}{m} \\
&= 2^{m}d_{m-1}+\frac{1}{2}\left [2^{m+1}d_m-\binom{n-1+m}{m}\right] \\
\end{aligned}
$$
然后
$$
\begin{aligned}
2^md_m &= 2^md_{m-1}-\frac{\binom{n-1+m}{m}}{2}\\
d_m &= d_{m-1}-\frac{\binom{n-1+m}{m}}{2^{m+1}}
\end{aligned}
$$
暴力算出 $d_0$ ，递推，然后求个前缀和就是 $f$ 了。
--------------------------
上周末刚好打了ARC150，刚好D题题解的 $O(n)$ 做法用到类似第一步的思想，不然我不会做（