【学习笔记】鞅和停时问题：一种构造势能函数的做法
有终止条件，随机操作，问期望多少次到达终止状态。
这是「鞅和停时」问题，可以构造势能函数满足每操作一次势能就降低 $1$，答案显然等于初势能 - 末势能。列等式解出初末势能。
$CF1349D-Slime and Biscuits$
势能法比概率做法不知道高到哪里去了！
我们希望构造势能函数 $\phi$ 和 $f$，其中 $\phi(A) = \sum\limits_{i = 1}^n f(a_i)$ 使得每操作一步，$\phi(A)$ 就减少 $1$。（真是神奇的定义啊）
$ans = 初势能 - 末势能 = ( \sum\limits_{i = 1}^{n} f_{a_i} ) - ( f_m + f_0 (n - 1) )$。也就是说 $\sum\limits_{i = 1}^n f_{a_i}$ 要比后继的期望大 $1$。即 $\sum\limits_{i = 1}^n f_{a_i} = \frac{1}{m} \sum\limits_{i = 1}^n a_i ( f_{a_i - 1} + \sum\limits_{j \neq i} (\frac{1}{n - 1} f_{a_j + 1} + \frac{n - 2}{n - 1} f_{a_j}) )$。化得 $\sum\limits_{i = 1}^n f_{a_i} = \sum\limits_{i = 1}^n \frac{a_i}{m} ( f_{a_i - 1} + 1 ) + f(a_i + 1) \frac{m - a_i}{m(n - 1)} + f(a_i) \frac{(n - 2)(m - a_i)}{(n - 1)m}$
再强调一次，是构造，怎么方便怎么来。强制钦定每个 $i$ 左右项都相等，则 $f(a) = \frac{a}{m} ( f(a - 1) + 1 ) + f(a + 1) \frac{m - a}{m(n - 1)} + f(a) \frac{(n - 2)(m - a)}{(n - 1)m}$。
这种和相邻若干项有关的方程组叫做 band-matrix。方程组个数为 $n$、与相邻 $d$ 项有关的 band-matrix 消元复杂度是 $O(nd^2)$，大概是竖着消且只消那 $d$/$2d$ 项？点我
另一种方便的解法是设 $f(i) = k_i f(m) + b_i$。钦定 $f(m - 1) = 0$，解出 $f(0 \cdots m - 2)$，根据 $f(0) = f(1)$ 再推回来。
$CF1479E-School Clubs$
设 $\phi(A) = \sum\limits_{i = 1}^m f(a_i)$
$\sum\limits_{i = 1}^m \frac{a_i}{n} \frac{1}{2} ( f(1) + f(a_i - 1) - f(a_i) + \sum\limits_{j \neq i} \frac{a_j}{n} ( f(a_j + 1) + f(a_i - 1) - f(a_i) - f(a_j) ) ) = -1$
$ans = \phi(A) - f(n)$
整理得
$\sum\limits_{i = 1}^m \frac{a_i}{n} ( 2 - f(a_i) + f(1) + f(a_i - 1) + \frac{n - a_i}{n}( f(a_i - 1) - f(a_i) ) + \frac{n - a_i}{n}( f(a_i + 1) - f(a_i) ) ) = 0$
更激进一点，令每项 $= 0$，推得
$f(x + 1) = \frac{1}{n - x} (-2n + (3n - 2x) f(x) - n f(1) - (2n - x ) f(x - 1))$
设 $f(0) = 0$, 为了方便令 $f(1) = -2$，递推即可。
4s 4e8，保留分数形式这样中途就不用求逆元了，选用 GNU C++17 (64) 就可以 AC 了。