Codeforces Round 641 (Div. 1)
D. Slime and Biscuits
https://codeforces.com/contest/1349/problem/D
第i个人有 ai 个饼干，在所有饼干中等概率选1个饼干 并把这个饼干 等概率 给其他人
当一个人有所有饼干时，游戏停止
问 期望时间 mod 998244353
n 100‘000
$\sum a_i \in [1,300’000]$
2s
256mb
我的思路
真没想法
题解
官方
令原游戏为$G$
$E_x=$ 所有游戏结束时，所有小饼干在x手里的情况 = $\sum p_{x,t}t$, 概率乘上时间的和
则$\mathrm{ans}=\sum_{x} E_x$
$G_x=$所有小饼干都在$x$手中才结束时的游戏 (和原题意不同)
令$F_x=$ 如果游戏$G_x$的期望时间(类似$E_x$).
令$P_x=$ 最终游戏$G$结束时所有小饼干都在 x手里的概率,
在游戏$G_j$中。常数$C$ 表示所有小饼干从$i$手里转移到$j$手里的期望时间
有神奇的等式
$E_x=F_x-\sum_{i=1,i\neq x}^n (P_i\cdot C+E_i)$
啊！？
也就是 $E_x=$所有在$G_x$中$x$结束的情况，减去其中先有其它$i$结束（按首次算）的情况，
1 | G_x 中对于 |
$\mathrm{ans}=\sum_{i=1}^n E_i=F_x-C\cdot \sum_{i=1,i\neq x}^n P_i$
$\mathrm{for} x= 1\cdots n$
$n \mathrm{ans}= \sum_{i=1}^n F_i - C(n-1)\cdot \sum_{i=1}^n P_i$
$\mathrm{ans}= \frac{1}{n}(\sum_{i=1}^n F_i - C(n-1))$
然后要计算$F_i$和$C$
令$A=\sum a_i$ 所有饼干的个数
对于游戏$G_i$关注玩家$i$有多少个饼干
设$f_m$为此时有$m$个饼干在$i$手中 到 游戏结束的剩余期望时间（发现其它玩家具体拿了多少是无关的, $C=F_0$）
$m = 0$时 $f_m=1+\frac{1}{n-1}f_{m+1}+\frac{n-2}{n-1}f_m$, 分别是拿了饼干 并给i,和拿了饼干给其它人
$0 < m < A$时 $f_m=1+\frac{A-m}{A}(\frac{1}{n-1}f_{m+1}+\frac{n-2}{n-1}f_m)+\frac{m}{A}f_{m-1}$, 分别是拿非$i$的饼干给i和不给i, 和拿i的饼干给别人
$m=A$时$f_m=0$ 目标状态
消元法可能 除法时除以0
整理一下上面表达式
$m = 0$时 $f_m-f_{m+1}=n-1$
$0 < m < A$时 $f_m=1+\frac{A-m}{A}(\frac{1}{n-1}f_{m+1}+\frac{n-2}{n-1}f_m)+\frac{m}{A}f_{m-1}$,
$f_{m}-f_{m+1}=(n-1)\frac{m}{A-m}((f_{m-1}-f_m)+\frac{A}{m})$,
$m=A$时$f_m=0$ 目标状态
分母都在mod意义下 非$0$， 可以推
评论区 戴江齐 大佬
https://codeforces.com/blog/entry/77284#comment-620956
类似于951F
$A=\sum_i a_i$
如果能找到 潜在 方程$f$ 使得$E(\sum_i f(a_i))$, 每一步 减少$1$, 其中$A$是所有$a_i$的和，（而$a_i$ 可以是和原问题的数字完全不同的值，这里的想法就是 如果总期望能表示成 基于每个点的函数表示，且能和 转移方程的变化拟合，那这个函数直接就可用！？！？，哇很好的神奇的直觉)
那么答案为$(\sum_i f(a_i)) - ((n-1)f(0)+f(A))$, 意思是初始的状态 减去 终止状态
$\sum_i f(a_i)=1+\sum_{i} \frac{a_i}{A}\left( f(a_i-1) + \sum_{j\neq i}(\frac{1}{n-1}f(a_j+1)+\frac{n-2}{n-1} f(a_j))\right)$
那么对于当前状态$[a_1,…,a_n]$, 那么拿第$i$个人的小饼干，则 概率为$\frac{a_i}{A}$, 右侧对于拿$i$后的新状态，
写得再简洁 就是$E(state)=1+\sum_{new state} p_{new state}E(new state)$
而猜想 存在$f$使得 $E(state) = \sum_{i} f(a_i)$，所以变成凑$f$的参数
那么对上面的整理(把$i$的整理到一起)为
$\sum_i f(a_i) = \sum_i \left(\frac{a_i}{A} (f(a_i-1)+1) + \frac{(A-a_i)}{A(n-1)} f(a_i+1)+\frac{(A-a_i)(n-2)}{n-1} f(a_i)\right)$
然后
$f(a)= \frac{a}{A} \left(f(a-1)+1\right)+\frac{A-a}{A(n-1)} f(a+1)+\frac{(A-a)(n-2)}{A(n-1)} f(a)$ 显然是一个 满足需求的方程式
直接过
总结
D: (3200评分)
https://codeforces.com/blog/entry/77284#comment-620956
这神奇的避开了$P_i$和$E_i$的计算，最后简化成了只和游戏$G_i$中，玩家$i$的当前持有关
核心就是要领悟 $E_x=F_x-\sum_{i=1,i\neq x}^n (P_i\cdot C+E_i)$ 带来的拆分
然后 戴江齐 大佬的对于这一类的 “潜在会分离 状态的 问题” 都可以这样搞 太强了，这数学直觉感太强了 orz, 哇 amazing
E:TODO
F1,F2:TODO