$取石子 II$取石子II

$\color{red}{正解部分}$正解部分

取石子 $1$1 传送门 .

点开传送门, 根据期望的线性, 答案可以当做每堆石子被取的期望次数和,
又因为 $a_i$ai​ 与 $a_1$a1​ 两堆石子是相互独立的, 因此可以单独计算贡献,

现在计算 $a_i$ai​, $a_1$a1​ 两堆石子的贡献,
将 $(a_1, a_i)$(a1​,ai​) 看做平面直角坐标系中的一个点,
从这个点出发 向左, 向下 进行随机游走, 当走到坐标轴时, 停止产生贡献,
接下来分情况讨论贡献,

• 走到 $(a, 0)$(a,0) 对答案的贡献为 $a_i$ai​, 概率为 $\sum\limits_{j=0}^{a_i-1} \begin{pmatrix} a_i+j-1\\ j \end{pmatrix} \frac{1}{2^{a_i+j}}$j=0∑ai​−1​(ai​+j−1j​)2ai​+j1​
• 走到 $(0, a)$(0,a) 对答案的贡献为 $a_i-a$ai​−a, 概率为 $\sum\limits_{j=0}^{a_i-1} \begin{pmatrix} a_1+j-1 \\ a_1-1 \end{pmatrix} \frac{1}{2^{a_1+j}}$j=0∑ai​−1​(a1​+j−1a1​−1​)2a1​+j1​

为了保证复杂度, 将走到 $(a, 0)$(a,0) 的概率换为 $\sum\limits_{j=0}^{a_i-1} (1 - \begin{pmatrix} a_1+j-1 \\ a_1-1 \end{pmatrix} \frac{1}{2^{a_1+j}})$j=0∑ai​−1​(1−(a1​+j−1a1​−1​)2a1​+j1​) .

则总期望贡献为 $\sum\limits_{j=0}^{a_i-1} a_i (1 - \begin{pmatrix} a_1+j-1 \\ a_1-1 \end{pmatrix} \frac{1}{2^{a_1+j}}) + \sum\limits_{j=0}^{a_i-1}j \begin{pmatrix} a_1+j-1 \\ a_1-1 \end{pmatrix} \frac{1}{2^{a_1+j}}$j=0∑ai​−1​ai​(1−(a1​+j−1a1​−1​)2a1​+j1​)+j=0∑ai​−1​j(a1​+j−1a1​−1​)2a1​+j1​

可以提前预处理出 $a_i \in [1, 5\times 10^5]$ai​∈[1,5×105] 的期望贡献, 之后 $O(N)$O(N) 计算即可 .

代码咕掉了.