CF1349D Slime and Biscuits
传送门
思路
果然对期望DP还没完全理解透啊，这道题不得不说太妙了
这道题的关键就是：设而不求，转化答案，破除界限
我们设以下变量：
\(E(x)\) 表示当结束时所有饼干都到 \(x\) 手上的期望，即在此之前饼干不曾集中在一个人手上
\(Es(x)\) 表示所有饼干集中到 \(x\) 手上才结束的期望，即之前可以存在饼干集中在除 \(x\) 的某一个人身上
\(P_x\) 表示结束时，所有饼干都在 \(x\) 手上的概率
\(C\) 表示当饼干已经集中在某个人手上时，将所有饼干集中到另一个人的期望步数
我们可以发现，其实 \(Es(x)=E(x)+(1-P_x)\times C+\sum_{i=1\ and\ i\not=x}^n E(i)=\sum_{i=1}^nE(x)+(1-P_x)\times C\)，
而答案 \(ans=\sum_{i=1}^n E(i)\)
结合两个式子，有 \(ans=Es(x)-(1-P_x)\times C\)
显然，因为结束时所有饼干一定会集中在某个人的手里，因此有 \(\sum_{i=1}^nP(i)=1\)
所以 \(\sum_{i=1}^n(Ex(i)-(1-P_i)\times C)=\sum_{i=1}^n Ex(i)-(n-1)\times C=n\times ans\)
这里我们成功将 \(E(x)\) 消去，转化为求限制没那么紧的 \(Es(x)\) 和 \(C\)
我们设 \(f_x\) 表示当某个人手上有 \(x\) 个饼干时，所有饼干都集中到他手里的期望
那么显然 \(Es(x)=f_{a[x]}, C=f_0\) （\(a[x]\) 表示 \(x\) 开始有的饼干数）
我们根据期望DP的套路就可以有以下表达式：（\(m\) 表示饼干的总数）
到这里其实就可以直接用带状矩阵消元用 \(O(n)\) 的时间做出来了，空间压缩一下数组就可以实现
但硅基生物大佬们注意到转移方程中的所有系数和都为 \(1\)，于是他们就开始了魔法操作
我们令 \(g_i=f_i-f_{i-1}\)，显然 \(f_i=\sum_{k=i}^m g_k,\ 0
那么根据那条一般的转移方程，我们有
\[\sum_{k=i}^m g_k=\frac{1}{m}\sum_{k=i-1}^m g_k+\frac{m-1}{m}\times (\frac{n-2}{n-1}\sum_{k=i}^m g_k+\frac{1}{n-1}\sum_{k=i+1}^m g_k)+1 \]通过拆拆拆消消消合并合并合并，我们可以化成一下式子：
\[g_i=\frac{1}{m}g_{i-1}+\frac{1}{m}g_i+\frac{(m-1)(n-2)}{m(n-1)}g_i+1 \]这是因为等式两边的 \(\sum_{k=i+1}^m\) 系数都为 \(1\) ，然后就消掉了
最后可以化成这个递推式：
\[g_i=\frac{i(n-i)}{m-i}g_{i-1}+\frac{m(n-1)}{m-i} \]至于 \(g_0\)，用第二条转移方程，相同方法可以直接算出 \(g_0=n-1\)
最后记得答案是 \(ans=\frac{\sum_{i=1}^nf_{a[i]}-(n-1)\times C}{n}\)
代码
#include
#include
#include
#include
#include
#include
#include
#include