题解 CF1025G 【Company Acquisitions】
skydogli
2020-10-06 22:36:48
感觉还没有窥探到这种势能函数的本质……先讲讲应用吧。
我们如果能给状态 $S$ 设定一种函数 $F(S)$ 使得每一次操作都会使 $F(S)$ 的期望增加 $1$,**且终止态无法继续转移**,那么我们就可以用$F(S_{end})-F(S_{begin})$ 来表示从当前态到终止态的期望。
至于为什么要求终止态无法转移,我们可以考虑一个有环的转移图是难以定义两点间的势能的,而终止态无法转移的话就可以避免这个问题。
这题我们尝试定义 $F(S)=\sum_{a_i\in S}f(a_i)$,其中 $a_i$ 表示有几个点跟随这个点。接下来我们尝试求出符合要求的 $f$。
因为每次操作的点是随机的,所以我们可以直接考虑值分别为 $a,b$ 的情况。
我们希望:
$$f(a)+f(b)+1=\frac{1}{2}[f(a+1)+(b-1)f(0)]+\frac{1}{2}[f(b+1)+(a-1)f(0)]$$
$f(0)$ 非常奇怪,但是我们定义的是**势能函数**,所以直接**钦定** $f(0)=0$ ,式子就变成了:
$$f(a)+f(b)+1=\frac{1}{2}[f(a+1)+f(b+1)]$$
由于对于任意 $a,b$ 都成立,所以 $f(x)$ 和 $f(x+1)$ 肯定有一个统一的关系,我们直接拆开:
$$f(a)+\frac{1}{2}=\frac{1}{2}f(a+1)$$
这显然可以是个等比数列的形式,令
$$f(a)+k=\frac{1}{2}(f(a+1)+k)$$
联立得 $k=1$。
也就是$f(a)=2^a-1$。
接下来直接计算即可。