题解 CF1025G 【Company Acquisitions】

skydogli

2020-10-06 22:36:48

Solution

感觉还没有窥探到这种势能函数的本质……先讲讲应用吧。 我们如果能给状态 $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$。 接下来直接计算即可。