2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1 [2020/05/17 20:38]
toxel 创建
+++ 2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1 [2020/05/17 21:34] (当前版本)
toxel add D
@@ 行 4: / 行 4: @@
 ====== Solutions ======
+===== D. Slime and Biscuits =====
+**题目大意**：有 $n$ 个口袋，每个口袋有 $a_{i}$ 个球。每次等概率随机一个球，将其等概率随机移动到另外 $n-1$ 个口袋中的一个。当所有球在同一个口袋时结束。问期望移动次数。
+**题解**：设 $E_{i}=\sum_{j=0}^{+\infty}jP_{ij}$，其中 $P_{ij}$ 表示在 $j$ 步后所有球在 $i$ 中的概率。注意 $E_{i}$ 本质上不是一个期望，因为其概率之和不为 $1$。答案为 $\sum_{i=1}^{n}E_{i}$。
+设 $E'_{i}$ 表示仅当所有球在 $i$ 中时游戏才结束的期望，$P_{i}=\sum_{j=0}^{+\infty}P_{ij}$。其中 $\sum_{i=1}^{n}P_{i}=1$。
+那么有 $E_{i}=E'_{i}-\sum_{j=1,j\neq i}^{n}(P_{j}E+E_{i})$，其中 $E$ 表示从所有球在口袋 $i$ 开始，直到所有球在口袋 $j(i\neq j)$ 结束的期望，显然这对任意 $i,j$ 都相同。
+将 $n$ 个式子相加可得，$n\cdot\text{ans}=\sum_{i=1}^{n}E'_{i}-(n-1)E$。
+至于 $E$ 和 $E'_{i}$ 的计算，则是经典的一维随机游走，这里就不赘述了。
+时间复杂度 $\mathcal{O}(\left(\sum_{i=1}^{n}a_{i}\right)\log\sum_{i=1}^{n}a_{i})$。

2020-2021/teams/intrepidsword/zhongzihao/codeforces_round_641_div._1.1589719086.txt.gz · 最后更改: 2020/05/17 20:38 由 toxel