好高妙！
大致思想是给每个局面构造一个势能函数 \(F(a_1, a_2, \ldots, a_n)\)，使得 \(\sum E(F(a'_1, a'_2, \ldots, a'_n)) - E(F(a_1, a_2, \ldots, n)) = -1\)，其中 \(a'\) 取遍 \(a\) 的后继状态。这样我们就能直接用终态的势能函数减去初始态的势能函数计算期望，即答案为 \(E(S) - E(T)\)。
可以考虑设 \(F(a_1, a_2, \ldots, a_n) = \sum\limits_{i = 1}^n f(a_i)\)。只要能构造出 \(f(x)\) 就能计算了。
1. 2024.2.26 模拟赛 T2 摸牌（cards）
设 \(g(x) = f(x) - f(x - 1)\)。推式子可以发现即要求：
\[\frac{x}{m} \times g(x) \times \frac{(n - 2)m + x}{(n - 1)m} - \frac{(m - x)^2}{(n - 1) m^2} \times g(x + 1) = \frac{1}{n} \]令 \(g(0) = 0\)，即可得到 \(g\) 的递推式，再做一遍前缀和即可得到 \(f(x)\)。
2. CF1025G Company Acquisitions
设 \(a_i\) 为 \(i\) 接着的点，设 \(F(a_1, a_2, \ldots, a_n) = \sum\limits_{i = 1}^n f(a_i)\)。即要求对于任意 \(x, y\)，都有：
\[\frac{1}{2} (f(x + 1) + y f(0)) + \frac{1}{2} (f(y + 1) + x f(0)) = f(x) + f(y) - 1 \]令 \(f(0) = 0\)，有：
\[\frac{1}{2} f(x + 1) + \frac{1}{2} f(y + 1) - f(x) - f(y) = -1 \]考虑 \(f\) 能满足这个条件的一个必要条件：
\[\frac{1}{2} f(x + 1) - f(x) = - \frac{1}{2} \]即 \(f(x + 1) = 2 f(x) - 1\)。递推计算即可。
标签：停时,势能,frac,定理,times,sum,ldots From： https://www.cnblogs.com/zltzlt-blog/p/18035649