鞅、停时定理
鞅，用来描述一种 公平、连续 随机过程。首先来看定义，这里只考虑离散意义下的鞅。
称随机过程 (X={X_n,nge 0}) 为 鞅，若
- (E(|X_n|)<infty)
- (E(X_{n+1}|X_0,cdots,X_n)=E(X_n))
称随机过程 (Y={Y_n,nge 0}) 是关于 (X) 的 鞅，若
- (Y_n) 仅仅与 (X_0cdots X_n) 有关；
- (E(Y_{n+1}|X_0,cdots,X_n)=E(Y_n))
直观来看，鞅就是一个随机过程：在已知前面所有 (s) 时刻之前的观测值，(s) 之后的期望与 (s) 时刻的期望相等。鞅描述了一种连续期望下的一种不动性。
随机时刻：设取值为 (Ncup{infty}) 的随机变量 (T)，及随机过程 ({X_n,nge 0})，若 (forall nge 0)，事件 ({T=n}) 的示性函数 (I_{{T=n}}) 仅仅是关于 (X_0,cdots,X_n) 的函数，则称 (T) 是随机过程 ({X_n,nge 0}) 的随机时刻。
停时：随机时刻 (T) 在不仅满足定义，并且满足 (P(T<infty)=1)，则称 (T) 是随机过程 ({X_n,nge 0}) 的停时。
停止过程：若 (T) 是对过程 ({X_n,nge 0}) 的一个随机时刻，称 (X_{nland T}) 为停止过程，其中 (aland b=min{a,b})。
不难证明停止过程也是关于 ({X_n,nge 0}) 的 鞅。
停时定理：假设 (M={M_n,nge 0}) 是关于 (X={X_n,nge 0}) 的鞅，(T) 是停时，(P(T<infty)=1)，有 (E(M_{nland T})=E(M_0)).
若满足下列三个条件之一：
- (|M_{nland T}|) 几乎处处有界 (Leftrightarrow |M_{nland T}|le K)；（( m bounded~in~space)）
- (T) 几乎有限 (Leftrightarrow P(Tle K)=1)；（( m bounded~in~time)）
- (E(T)<infty)，并且 (E(|M_{n+1}-M_n|mid X_0cdots X_n)le K)；（( m bounded~in~increments)）
则有 (E(M_T)=E(M_0)) 成立。
猴子打字问题
给定字符集大小为 (m)，长度为 (n) 的串 (s)。初始时，令字符串 (t=phi)，每次在 (t) 后面随机加入一个字符。求 (s) 第一次成为 (t) 后缀的期望时间。
常规做法：设 (F(x)) 表示不同长度下，(s) 第一次成为 (t) 后缀的概率生成函数，(G(x)) 表示不同长度下，(s) 没有成为 (t) 后缀的概率生成函数。
在 (G) 后加任意一个字符，只会变成 (F) 和 (G) 的一种，得到
在 (G) 后面添加 (s)，有可能提前成为 (F)，成为 (F) 之前加入的部分一定为 ( m border)。设 (c(x)=sum_{i=1}^n[s[1,i]=s[n-i+1,n]](frac xm)^{n-i})，得到
联立得到
期望为 (F'(1))。两边求导后代入 (F(1)=1) 和 (x=1)，即可得到结果为 (sum_{i=1}^n[s[1,i]=s[n-i+1,n]]m^i)。
使用 停时定理 也可求解。
假设在每个时刻，有一个赌徒拿着 1 元钱入场，并押当前这一次随机的字符为 (s_1)。如果没押中，输光离场；押中了，资金变成 (m) 倍。下一次他押 (s_2)，同样按照刚刚的方法；下一次押 (s_3)、(s_4)、(cdots)，直到押中 (s_n) 为止，此时他有 (m^n) 元钱，或者输光离场。
不难发现每个赌徒在任何时候的 期望收益 为 0，在第 (t) 个时刻后，设所有赌徒的 金额总和 期望为 (A_t)，则 ({A_t-t,tge 0}) 是鞅。
设 (T=min{x:t[n-x+1,n]=s})，则 (T) 是一个停时，同时 (0le A_{tland T}-tland Tle sum_{i=1}^nm^i-n) 有界，由停时定理得到
而
故
(E(A_T)) 的意义为：(T) 到来时（即结束时），所有赌徒的金额总和。显然上式成立。
势能函数
我们发现求解这类问题的关键，就是选取一个好的鞅，利用停时定理求解方程。这时，构造一个好的 势能函数 将会大有功用。
给定随机序列 (A={A_n,nge 0})，(T) 为停时，求 (E(T))。
构造势能函数 (Phi(A))，满足：
- (E(Phi(A_{n+1})-Phi(A_n)|A_0,cdots,A_n)=-1)；
- (Phi(A_T)) 为常数，且 (Phi(A_i)=Phi(A_T)) 当且仅当 (i=T)；
构造序列 (X_n=Phi(A_n)+n)，则 (X={X_n,nge 0}) 是关于 (A) 的鞅。
利用停时定理，得到：(E(X_T)=E(X_0))，即 (E(Phi(A_T)+T)=E(Phi(A_0))Rightarrow E(T)=E(Phi(A_0))-Phi(A_T))。
CF1025G Company Acquisitions
给定 (n) 个节点，每个节点要么为根，要么父亲为根；
现在有一种操作：等概率选取两个 不同的根 (x) 和 (y)（关心顺序），将 (y) 的所有孩子变成根（有可能没有），(y) 的父亲设成 (x)。
该操作当且仅当只剩下一个根时结束。
询问期望操作数，对 (10^9+7) 取模。(n le 500)。
做法：设一棵有 (x) 个孩子的树的势能为 (f(x))，当前局面势能 (Phi(A)=sum_{a_iin A}f(a_i))。对于操作，假设两棵树的孩子分别为 (x) 和 (y)，操作完成以后，对于先后状态的变化关系，根据 (x ightarrow y) 和 (y ightarrow x) 的概率各占一半，利用上面的公式，我们可以列出
由于是势能，我们不关心 (f(0)) 的值，不妨设 (f(0)=0)，得到
由于对于任意 (x,y) 方程均成立，我们可以写出
解得 (f(x)=1-2^x)
依据停时定理，最后求起末状态的势能差即可。
CF850F Rainbow Balls
袋子里有 (n) 种颜色的球，第 (i) 种颜色有 (a_i) 个。
每次操作：等概率取出两个球 (x) 和 (y)（有序），将 (y) 的颜色变成 (x) 的颜色。操作直到所有球颜色相同时停止。
期望多少次操作后停止。答案对 (10^9+7) 取模。
(nle 2500)，(a_ile 10^5)。
常规做法：设 (f_i) 表示当下某种颜色的球有 (i) 个，该颜色能成为成为最终所有球的颜色时的期望次数。首先 (f_i) 是条件期望，由全期望公式，答案就是
(p_{a_i}) 表示某种颜色有 (a_i) 个，其能成为最终颜色的概率。
第一步，我们要求解 (p_i)。假设 (s=sum_{i=1}^na_i)，不难列出
易知 ({p}) 成等差，代入 (p_0=0) 和 (p_s=1) 得到 (p_i=frac is)。
现在列期望的方程。由条件期望得到
令 (g_i=if_i-(i-1)f_{i-1})，有 (g_{i+1}=g_i-frac{s(s-1)}{s-i}) 成立，再令 (h_i=g_{i+1}-g_{i}=-frac{s(s-1)}{s-i})，则 (g_n=g_1+sum_{i=1}^{n-1}h_i)，(nf_n=sum_{i=1}^ng_i=ng_1+sum_{i=1}^{n-1}(n-i)h_i)，代入 (f_s=0) 得到
剩余部分线性递推即可。复杂度 (mathcal O(max a_ilog P))。
势能法：定义 (f(x)) 表示同种颜色有 (x) 个球的势能，当前局面势能 (Phi(A)=sum_{a_iin A}f(a_i))。对于操作：我们有 (frac{a_i(a_i-1)}{s(s-1)}) 的概率选出来两个相同颜色的球，有 (frac{a_ia_j}{s(s-1)}) 的概率将 (i) 变成 (j)。
于是有
最后一步利用 ((i,j)) 和 ((j,i)) 对调部分项得到。
继续
我们希望这个式子恒成立，于是直接令
似曾相识？！基本上跟上面一样了。
CF1349D Slime and Biscuits
有 (n) 个人，第 (i) 个人拥有 (a_i) 块饼干。
每次操作，等概率随机一块饼干，假设这是 (x) 的饼干，再等概率随机除 (x) 外的一个人 (y)，将 (x) 的这块饼干交给 (y)。该过程直到一个人拥有所有饼干。
求期望操作次数。(nle 10^5)，(sum a_ile3 imes10^5)。
常规做法：（咕咕咕）
势能法：令 (S=sum a_i)，设 (f(x)) 表示某个人有 (x) 块饼干时的势能，当前局面总势能 (Phi(A)) 为 (sum_{a_iin A}f(a_i))。老生常谈，写出
方便地，我们令
令 (f(0)=0)，代入 (x=0)，解得 (f(1)=0)。于是可以快乐地线性递推。
最后求势能差即可。
自己在一道题目上的尝试
（树上移动）：给定一棵 (n) 个节点的树，(i) 号节点的父亲为 (f_i(f_i<i))。每个节点的颜色要么为黑，要么为白。起始时，等概率随机一个节点作为起点。之后每一次，从 (n) 个点中等概率选取一个节点 (x)，从当前点走到 (x)，并且翻转节点 (x) 的颜色（黑->白 或者 白->黑）。该过程直到所有节点都变成白色或者黑色时停止。求期望走过的路径长度和，答案对 (10^9+7) 取模。
(nle 10^5)。
这道题是我自己想出来利用 停时定理，构造一个合适的鞅来求解，希望能够起到抛砖引玉之效。
首先该问题与之前的问题不太一样：之前要求解期望时间，而这里要求解期望路径长度。势能法不能直接运用于此。
首先我们来描述这个随机游走的过程。
设 (X_n) 表示第 (n) 个时刻下关于点的随机变量，其中每个点等概率；(E[Y_n]) 表示第 (n) 个时刻，期望走过的路径长度和。根据定义有 (E[Y_n]=E[sum_{i=1}^n{ m dis}(X_{i-1}, X_i)])。
令停时 (T) 表示所有节点第一次全部变成白/黑的时刻，该随机时刻描述了何时过程结束。我们的问题就是要求解 (E[Y_T]) 的值。
令 (overline d=frac{sum_{x,y}{ m dis}(x,y)}{n^2})，显然 (E[{ m dis}(X,X)]=overline d)。令 (overline{d_x}=frac{sum_y{ m dis}(x,y)}n)，显然 (E[{ m dis}(x,X)]=overline{d_x})。
为了构成鞅，我们考虑令 (Z_n=Y_n-noverline d)。但遗憾的是，根据鞅的定义，(E[Z_{n+1}|X_0,cdots,X_n]) 可能不等于 (E[Z_n|X_0,cdots,X_n])，也就是说 (Z) 不是鞅！最主要的原因：(E[Z_{n+1}|X_0,cdots,X_n]) 与 (X_n) 相关！(Y) 的增量可能小于（或大于）(overline d)，比如 (E[{ m dis}(x, X)]<E[{ m dis}(X,X)])，这些增量无法通过后面减法的部分配平。
仔细思考发现 (E[Y_{n+1}|X_0,cdots,X_n]) 仅仅与 (X_n) 相关！即 (E[Y_{n+1}|X_0,cdots,X_n]=E[Y_{n+1}|X_n])。我们来尝试构造函数 (f(X)) 来辅助配平式子，也就是让
成立。
于是我们尝试列方程。由于 (X_n) 已知，假设 (X_n=x)，能得到
该式对于任意 (x) 均成立。直接令 (f(x)=overline{d_x}-overline d) 即可。
这样，令 (Z_n=Y_n+f(X_n)-noverline d)，(Z) 将关于 (X) 构成鞅。不难得出 (E(T<infty)=1)，并且根据构造，(E[|Z_{n+1}-Z_n|]) 显然有界，于是乎可以利用 停时定理 了！
其中
({ m Pr}(X_T=x)) 的意义是：最后一次翻转的点为 (x) 的概率。(E[T]) 表示期望操作次数。两者直接列 DP 求解即可。
回顾刚刚的过程，我们发现：鞅和停时定理的运用，可以帮助我们转化问题、简化问题，避免某些复杂的状态设计，甚至有可能在消元上都要折磨大家（本题的一种常规做法在消元上较为麻烦）。求解问题的关键，就是选取一个合适的鞅，有时为了构造鞅，甚至需要构造合适的函数，结合停时赋予的实际意义，这样转化会变得十分方便。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5 + 5, P = 1e9 + 7;
int n, fa[N], siz[N], dis[N], dep[N], sdep, inv[N], cnt;
char s[N];
void upd(int &a, ll b) { (a += b) %= P; }
int qpow(int a, int b) {
int c = 1;
for (; b; b >>= 1, a = (ll)a * a % P)
if (b & 1) c = (ll)c * a % P;
return c;
}
struct Data {
int x, y;
Data(int x = 0, int y = 0) : x(x), y(y) {}
Data operator + (Data o) { return Data((x + o.x) % P, (y + o.y) % P); }
Data operator - (Data o) { return Data((x - o.x + P) % P, (y - o.y + P) % P); }
Data friend operator * (Data o, ll k) { return Data(k * o.x % P, k * o.y % P); }
int v(int o) { return ((ll)x * o + y) % P; }
} f[N], g[N];
int main() {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++)
siz[i] = 1, cnt += s[i] == '1';
inv[1] = 1;
for (int i = 2; i <= n; i++)
scanf("%d", &fa[i]), inv[i] = (ll)(P - P / i) * inv[P % i] % P;
for (int i = n; i > 1; i--) upd(siz[fa[i]], siz[i]);
for (int i = 1; i <= n; i++)
dis[i] = (dis[fa[i]] - siz[i] + P) % P, upd(sdep, dep[i] = dep[fa[i]] + 1);
for (int i = 1; i <= n; i++)
upd(dis[0], dis[i] = (dis[i] * 2 + (ll)n * dep[i] + sdep) % P * inv[n] % P);
dis[0] = (ll)dis[0] * inv[n] % P;
f[1] = g[1] = {1, 0};
for (int i = 1; i < n; i++)
f[i + 1] = ((f[i] * n * inv[i] - f[i - 1]) * (i + 1) - Data(0, inv[i])) * inv[n - i - 1],
g[i + 1] = (g[i] * n - g[i - 1] * i - Data(0, n)) * inv[n - i];
int x = (ll)(P + 1 - f[n - 1].y) * qpow(f[n - 1].x + n - 1, P - 2) % P, y = (ll)(P - g[n].y) * qpow(g[n].x, P - 2) % P;
int ans = (ll)dis[0] * g[cnt].v(y) % P;
for (int i = 1; i <= n; i++)
ans = (ans - (ll)(dis[i] - dis[0]) * (f[s[i] == '0' ? cnt : n - cnt].v(x) - inv[n]) % P + P) % P;
printf("%d
", ans);
return 0;
}