初始状态的势函数减去终止状态的势函数即为期望。

CF1349D Slime and Biscuits

设 \(m=\sum a_i\)。

\[\large\begin{aligned} f(x)&=\frac{x}{m}+\frac{x}{m}f(x-1)+\frac{m-x}{m(n-1)}f(x+1)+\frac{(m-x)(n-2)}{m(n-1)}f(x) \end{aligned} \]

CF850F Rainbow Balls

设 \(m=\sum a_i\)。

\[\large\begin{aligned} f(x)&=\frac{x}{m}+\frac{x(x-1)+(m-x)(m-x-1)}{m(m-1)}f(x)+\frac{x(m-x)}{m(m-1)}(f(x+1)+f(x-1))\\ 0&=\frac{x}{m}+\frac{x(m-x)}{m(m-1)}(f(x+1)+f(x-1)-2f(x))\\ \end{aligned} \]

CF1025G Company Acquisitions

\[\large\begin{aligned} f(x)+f(y)&=1+\frac{1}{2}\left( f(x+1)+yf(0) \right)+\frac{1}{2}\left( f(y+1)+xf(0) \right)\\ f(x)+f(y)&=1+\frac{1}{2}f(x+1)+\frac{1}{2}f(y+1)\\ f(x)&=\frac{1}{2}+\frac{1}{2}f(x+1)\\ f(x)&=1-2^x\\ \end{aligned} \]