初始状态的势函数减去终止状态的势函数即为期望。
CF1349D Slime and Biscuits
设 (m=sum a_i)。
[largeegin{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)。
[largeegin{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
[largeegin{aligned}
f(x)+f(y)&=1+frac{1}{2}left( f(x+1)+yf(0)
ight)+frac{1}{2}left( f(y+1)+xf(0)
ight)\
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}
]