本文基本不做证明，只简单说明大致内容，由于博主只是一只猫没有数理基础，有错误还望指出（其实大部分在搬 wiki）。
鞅
鞅最早指一种赌博策略，所以本文会把其和赌博策略部分联系起来。
定义离散时间鞅（本文只讨论离散时间的情况）为满足以下条件的随机过程（依赖于时间的随机变量序列） \(X_0,X_1,X_2,\dots\)
- \(\forall n\in\mathbb{N},\mathbf{E}[X_n]<\infty\)。
- \(\forall n\in\mathbb{N+},\mathbf{E}[X_{n+1}\mid X_n,X_{n-1},\dots,X_0]=X_n\)。
第一条比较平凡，第二条用比较通俗的语言讲，就是已知之前的所有观测值，下一次观测值的期望等于这一次观测值。
同时有更为一般的定义，若
- \(\forall n\in\mathbb{N},\mathbb{E}[Y_n]<\infty\)。
- \(\forall n\in\mathbb{N+},\mathbb{E}[Y_{n+1}\mid X_n,X_{n-1},\dots,X_0]=Y_n\) 。
则称随机过程 \(Y_0,Y_1,\dots\) 是关于另一随机过程 \(X_0,X_1,\dots\) 的鞅。
容易证明，对于任意 \(n\in\mathbb{N+},\mathbf{E}[X_n]=X_0\)，也就是认为 \(X_0,X_1,\dots\) 是赌徒的财产，则无论赌多少次，赌徒最后的期望财产依旧等于他最开始的财产。
下面举几个鞅的例子：
设 \(X_n\) 表示一个赌徒抛掷了 \(n\) 次公平硬币（正反面概率相等）后的财产。规则是若为正面朝上，则获得 1 元；反之输掉 1 元。在已知过去所有时刻的财产下，若赌徒再抛掷一次硬币，显然抛掷完后财产的期望依旧等于现在的财产数量。故 \(X_0,X_1,X_2,\dots\) 这一随机过程是鞅。
接着上面的例子，设 \(Y_n=X_n^2-n\)，则 \(Y_0,Y_1,\dots\) 这一随机过程是关于随机过程 \(X_0,X_1,\dots\) 的鞅，证明如下： \[ \begin{aligned} \mathbf{E}[Y_{n+1}]&=\frac{(X_n-1)^2-(n+1)+(X_n+1)^2-(n+1)}{2}\\ &=\frac{1}{2}(X_n^2-2X_n+1-n-1+X_n^2+2X_n+1-n-1)\\ &=\frac{1}{2}(2X_n^2-2n)\\ &=X_n^2-n=Y_n \end{aligned} \] 注意到 \(\mathbf{E}[Y_n]=\mathbf{E}[X_n^2]-n=\mathbf{E}[X_0^2]\)，取 \(X_0=0\) 则 \(\mathbf{E}[X_n^2]=n\)，如果 \(X_0\not=0\) 只需要把 \(Y_n\) 定义为 \((X_n-X_0)^2-n\) 即可，这一例子可以表明赌徒的全部收益或损失大致在抛掷次数的正负平方根之间变化。
停时与鞅的停时定理
对于一列随机变量 \(X_0,X_1,\dots\)，停时 \(\tau\) 为一个随机变量，满足性质：对于任意时间 \(t\)，事件 \(\tau=t\) 是否发生仅取决于 \(X_0,X_1,\dots\) 的取值。也就是说我任意时间只根据我现在获得的信息我都知道是否已经停下，而不需要根据将来的信息。
现在令 \(X_0,X_1,\dots\) 为一鞅过程，\(\tau\) 为该过程的停时，且 \(\tau\in\mathbb{N}\cup\{\infty\}\)，则当以下三个条件至少有一个成立时，有 \(\mathbf{E}[X_\tau]=X_0\)：
- \(\tau\) 几乎一定有界。
- \(|X_{t+1}-X_{t}|\) 一致有界，且 \(\mathbf{E}[\tau]\) 有限。
- \(X_t\) 一致有界，且 \(\tau\) 几乎一定有限。
“几乎一定”指概率为 \(1\)；有限指不能取无穷；有界指存在常数 \(m,M\)，使得取值在区间 \([m,M]\) 内；一致有界指对于任意 \(t\)，\(X_t\)（第二条同理）均有界。
证明就不写了（还是因为博主太菜了），有兴趣可以自行查找。
请注意它和鞅的性质中对任意 \(n\in\mathbb{N+},\mathbf{E}[X_n]=X_0\) 的区别，这条中 \(n\) 是确定的，而停时定理中 \(\tau\) 是一个随机变量，而且 \(\mathbf{E}[x_\tau]=X_0\) 是不一定的（反例可以考虑只有一个终点的一维随机游走）。
下面我们回到 OI，OI 中我们一般会利用停时定理求给定随机过程 \(A_0,A_1,\dots\) 的停时的期望 \(\mathbf{E}[\tau]\)。具体地，如果我们能构造势能函数 \(\phi\)，如果我们能让 \(\mathbf{E}[\phi(A_{t+1})-\phi(A_t)\mid A_0,A_1,\dots,A_t]=-1\)，则我们构造随机过程 \(X_t=\phi(A_t)+t\)，则 \(\mathbf{E}[X_{t+1}-X_t\mid A_0,A_1,\dots,A_t]=0\)，也就是说 \(X_0,X_1,\dots\) 是鞅。如果 \(\tau\) 也是 \(X_0,X_1,\dots\) 的停时，那么根据停时定理我们有 \(\mathbf{E}[X_\tau]=X_0\)，即 \(\mathbf{E}[\phi(A_\tau)+\tau]=\phi(A_0)\)，故 \(\mathbf{E}[\tau]=\phi(A_0)-\phi(A_\tau)\)，由于 \(A_0,A_\tau\) 是题目给出的所以是确定的。
\(\phi\) 的构造是有一定条件的，比如你不能构造 \(\phi(A_t)=-t\)，因为期望会被消掉；同时要保证 可以根据 \(\phi(A)\) 确定出 \(A\) 是否为目标状态，否则无法找到令 \(\tau\) 也是 \(X_0,X_1,\dots\) 的停时的条件。
例题1：有初始大小为 \(n\) 的可重集 \(a\)，现在定义每一次操作为随机选出两个元素 \(a_i,a_j\)，有 \(p\) 的概率令 \(a_i\leftarrow a_i+1\)，删除 \(a_j\) 并添加 \(a_j-1\) 个 \(1\) 到 \(a\) 中；有 \(p\) 的概率把上面 \(i,j\) 反过来然后结果和上面一样；否则删除 \(a_i,a_j\) 并添加 \(a_i+a_j\) 个 \(1\) 到 \(a\) 中。问集合只有一个元素的期望操作次数，对 \(10^9+7\) 取模。\(n\leqslant 4\times 10^7\)。
首先一般情况如果一个局面有多个元素，我们一般可以让势能函数为每个元素的势能之和，即 \(\phi(X_i)=\sum f(a_{i,j})\)。
我们考虑解出这个函数 \(f\)，假设第 \(m\) 次操作的两个元素为 \(a_i,a_j\)，则有： \[ \begin{aligned} &\mathbf{E}[\phi(m+1)-\phi(m)]\\ =&p(f(a_i+1)+(a_j-1)f(1)-f(a_i)-f(a_j))\\ &+p(f(a_j+1)+(a_i-1)f(1)-f(a_i)-f(a_j))\\ &+(1-2p)((a_i+a_j)f(1)-f(a_i)-f(a_j))\\ =&-1 \end{aligned} \] 我们可以设 \(f(1)=0\)，这样我们发现能够消去很多的项，则有： \[ pf(a_i+1)-f(a_i)+pf(a_j+1)-f(a_j)=-1 \] 我们需要让 \(f\) 的变化和选取的 \(a_i,a_j\) 无关，所以有 \[ pf(n+1)-f(n)=-\frac{1}{2}\\ f(n+1)=\frac{1}{p}f(n)-\frac{1}{2p} \] 这种 \(f(n)=kf(n-1)+b\) 的递推式一定能通过设 \(f(n)+c=k(f(n-1)+c)\)，然后解出 \(c\)，就是一个等比数列的形式，这题中 \(c=\dfrac{1}{2(p-1)}\)，故 \(f(n)=\dfrac{1}{2(p-1)}(p^{-n+1}-1)\)。
注意到终止态 \(\phi\) 唯一最小，所以直接使用停时定理求出 \(\phi(X_0)\) 与 \(\phi(X_\tau)\) 即可，需要一个光速幂（分块预处理 \(p^{-1}\) 的幂）。
代码可以见校内 OJ 的提交记录，需要注意的是在指数上的数要对 \(10^9+6\) 取模。