鞅与停时定理 例题记录

鞅与停时定理，一个很厉害的东西，感觉像是一种势能分析。

关于它具体是什么，笔者的数学水平还不足以讲述，所以在这里推广一下：概率论科技：鞅与停时定理 - littleZ_meow 的小窝。

下面的写法可能很不专业，请自行避雷。

给出一种很 OI 的解释：你需要设计一个函数 \(f(x)\)，有次能够得到每一个状态的势能 \(F(S)=\sum\limits_{a\in S}f(a)\)，记 \(S'\) 为对于集合 \(S\) 操作一步可能达到的状态。你需要找到一个合适的函数 \(f(x)\)，使得 \(F(S)+1=E(F(S'))\) 恒成立，且终止状态不会再发生任何转移，则需要操作的期望步数为 \(F(S_t)-F(S_0)\)。

也就是你要有一个势能函数，使得无论如何，每一次操作势能都期望增加 1。

CF1025G Company Acquisitions

记 \(f(x)\) 表示一个选定点下面挂 \(x\) 个未选定点的势能函数。

由于和式的项数是变化的，所以我们只考虑操作了的 \(x\) 和 \(y\)。
我们有 \(f(x)+f(y)+1=\dfrac{1}{2}(f(x+1)+yf(0))+\dfrac{1}{2}(f(y+1)+xf(0))\)。

由于对于任意的 \(x\) 成立，则 \(f(x)+\dfrac{1}{2}=\dfrac{1}{2}f(x+1)+\dfrac{x}{2}f(0)\)。

令 \(f(0)=0\)，可以得到 \(f(x)=2^x-1\)。

最终状态的势能为 \(f(n)=2^n-1\)，初始状态的势能为 \(\sum f(a_i)\)。

CF1349D Slime and Biscuits

记 \(f(x)\) 表示有 \(x\) 块饼干的人的势能，\(A=\sum\limits_{i=1}^na_i\)。

考虑 \(E(F(S'))=F(S)+1\)。

则 \(\sum\limits_{i=1}^nf(a_i)+1=\sum\limits_{i=1}^n\frac{a_i}{A}(f(a_i-1)+\frac{1}{n-1}\sum\limits_{j\neq i}(f(a_j+1)+\sum\limits_{k\neq j} f(a_k)))\)。

有 \(\sum\limits_{i=1}^nf(a_i)+1=\sum\limits_{i=1}^n(\frac{a_i}{A}f(a_i-1)+\frac{A-a_i}{A}\times \frac{1}{n-1}f(a_i+1)+\frac{A-a_i}{A}\times \frac{n-2}{n-1}f(a_i))\)。

对于任意的 \(S\) 成立。

则 \(f(x)+\frac{x}{A}=\frac{x}{A}f(x-1)+\frac{A-x}{A}\times \frac{1}{n-1}f(x+1)+\frac{A-x}{A}\times \frac{n-2}{n-1}f(x)\)。

整理得 \(f(x+1)=\left[\frac{A(n-1)}{A-x}-(n-2)\right]f(x)-\frac{(n-1)x}{A-x}f(x-1)+\frac{(n-1)x}{A-x}\)。

我们令 \(f(0)=f(1)=0\)，可以直接递推出所有的 \(f(x)\)。

CF1479E School Clubs

记 \(f(x)\) 表示有 \(x\) 个人得社团的势能，\(A=\sum\limits_{i=1}^ma_i\)。

我们有 \(\sum\limits_{i=1}^mf(a_i)+1=\sum\limits_{i=1}^m\frac{a_i}{A}\left(\frac{1}{2}\left(\sum\limits_{i\neq j}f(a_j)+f(a_i-1)+f(1)\right)+\frac{1}{2}\left(\sum\limits_{j\neq i}\frac{a_j}{A}\left(f(a_j+1)+f(a_i-1)+\sum\limits_{k\neq i,k\neq j}f(a_k)\right)+\frac{a_i}{A}(\sum\limits_{j=1}^nf(a_j))\right)\right)\)

对于任意的 \(S\) 成立。

则 \(f(x)+\frac{x}{A}=\frac{A-x}{2A}f(x)+\frac{x}{2A}(f(x-1)+f(1))+\frac{x^2}{2A^2}f(x)+\frac{x(A-x)}{2A^2}f(x-1)+\frac{x(A-x)}{2A^2}f(x+1)+\frac{(A-x)(A-x)}{2A^2}f(x)\)。

为了消去常数项，我们令 \(f(1)=2\)。

整理得 \(f(x+1)=\frac{3A-2x}{A-x}f(x)-\frac{2A-x}{A-x}f(x-1)\)。

可以得到 \(f(x+1)-f(x)=\frac{2A-x}{A-x}(f(x)-f(x-1))\)。

记 \(g(x)=f(x+1)-f(x)\)，则有 \(g(x)=\frac{2A-x}{A-x}g(x-1)\)，由此可以 \(O(n)\) 计算出 \(f(n)\)，把每个数拆成分子分母维护，注意一下常数（开一个 C++20）就可以过了。

CF850F Rainbow Balls

记 \(f(x)\) 为有 \(x\) 个球的颜色的势能，\(A=\sum\limits_{i=1}^na_i\)。

考虑 \(E(F(S'))=F(S)+1\)。

我们有 \(\sum\limits_{i=1}^nf(a_i)+1=\sum\limits_{i=1}^n\frac{a_i}{A}\left(\sum\limits_{j\neq i}\frac{a_j}{A-1}\left(f(a_i+1)+f(a_j-1)+\sum\limits_{k\neq i,k\neq j}f(a_k)\right)+\frac{a_i-1}{A-1}\sum\limits_{j=1}^nf(a_j)\right)\)。

对于任意的 \(S\) 成立。

则 \(f(x)+\frac{x}{A}=\frac{x(A-x)}{A(A-1)}f(x+1)+\frac{x(x-1)}{A(A-1)}f(x)+\frac{(A-x)x}{A(A-1)}f(x-1)+\frac{(A-x)(A-x-1)}{A(A-1)}f(x)\)。

整理得 \(f(x+1)=2f(x)-f(x-1)+\frac{A-1}{A-x}\)。

令 \(f(0)=0\)。

初始态的 \(\sum\limits_{i=1}^nf(a_i)\) 是好求的，但是我们还有求一个 \(f(A)\)，这个是无法递推的。

考虑 \(f(x+1)-f(x)=f(x)-f(x-1)+\frac{A-1}{A-x}\)。

记 \(g(x)=f(x+1)-f(x)\)，则 \(g(x)=g(x-1)+\frac{A-1}{A-x}\)。

有 \(g(x)=g(0)+\sum\limits_{i=1}^x\frac{A-1}{A-i}\)。

令 \(g(0)=0\)，有 \(g(x)=\sum\limits_{i=1}^x\frac{A-1}{A-i}\)。

所以 \(f(x)=f(0)+\sum\limits_{i=0}^{x-1}g(i)=\sum\limits_{i=0}^{x-1}\sum\limits_{j=1}^i\frac{A-1}{A-j}\)。

所以 \(f(x)=\sum\limits_{i=1}^{x-1}\frac{(A-1)(x-i)}{A-i}\)。

所以 \(f(A)=\sum]limits_{i=1}^{A-1}\frac{(A-1)(A-i)}{A-i}=(A-1)^2\)。

这样就解决了计算 \(f(A)\) 的问题。

小结

对于后三题这种每一次调整 \(1\) 的题目，发现最后整理出来的式子都是 \((A+B)f(x)=Af(x+1)+Bf(x-1)+C\) 的形式，这提醒我们在递推有困难的时候可以考虑转成差分的形式处理，可能会有很好的效果。