如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
离散时间鞅
定义离散时间鞅为一个时间离散的随机过程 ${X_0,X_1,\cdots}$，使得 $\forall n\in \N$，均满足：
- $E(\mid X_n\mid)<\infty$；
- $E(X_{n+1}-X_n\mid X_0,X_1,\cdots,X_n)=0$；
根据这个，容易得到 $E(X_n)=X_0$。
停时定理
设 $t$ 为鞅过程 ${X_0,X_1,\cdots}$ 的停时，当下面三个条件之一成立时，有 $E(X_t)=X_0$：
- $t$ 几乎必然有界；
$E( X_{i+1}-X_i )$ 一致有界，$E(t)$ 有限； - $X_i$ 一致有界，$t$ 几乎必然有限。
名词解释：
- $a\in\mathbb{R}\cup{\infty}$ 有限：$\mid a\mid <\infty$；
- $a\in\mathbb{R}\cup{\infty}$ 有界：$\exists l,r\in \mathbb{R},a\in[l,r]$；
- $a_i\in\mathbb{R}\cup{\infty}$ 一致有界：$\forall i,\exists l,r\in \mathbb{R},a_i\in[l,r]$；
- 事件 $A$ 几乎必然发生：$P(A)=1$。
势能函数
对于随机时间序列 ${A_0,A_1,\cdots}$，$t$ 为其停时，终止状态为 $A_t$，求 $E(t)$。
构造势能函数 $\Phi(A)$，满足：
- $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$；
- $\Phi(A_t)$ 为常数，且 $\Phi(A_i)=\Phi(A_t)$ 当且仅当 $i=t$。
构造序列 $X_i=\Phi(A_i)+i$，则 $E(X_{n+1}-X_n\mid X_0,X_1,\cdots,X_n)=0$，即 ${X_0,X_1,\cdots}$ 是鞅。
根据停时定理，我们可以得到 $E(X_t)=E(X_0)$，即 $E(t)=E(\Phi(A_0))-\Phi(A_t)$。
例题
CF1025G Company Acquisitions
设 $f(x)$ 为跟随有 $x$ 个未选中点的选中点的势能函数，整个局面的势能函数为 $\Phi(A)$，每个选中点的势能函数的和。
显然每次操作的势能变化量只和随出来的两个点有关，$u,v$ 的儿子数设为 $x,y$。
为满足 $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有
\[f(x)+f(y)-1=\frac{1}{2}(f(x+1)+yf(0))+\frac{1}{2}(f(y+1)+xf(0))\]因为我们要对于任意 $x,y$ 成立，所以
\[f(x)-\frac{1}{2}=\frac{1}{2}f(x+1)+\frac{x}{2}f(0)\]取 $f(0)=0$，则 $f(x)=1-2^x$。
设停时为 $t$，注意到 $\Phi(A_t)=f(n-1)=1-2^{n-1}$ 为常数，所以 $E(t)=\Phi(A_0)-\Phi(A_t)$。
#include<cstdio>
int const mod=1e9+7;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int n,c[510],ans;
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(~x)++c[x];
}
for(int i=1;i<=n;i++)ans=(ans+1-pow(2,c[i])+mod)%mod;
ans=(ans+pow(2,n-1)-1)%mod;
if(ans<0)ans+=mod;
printf("%d\n",ans);
return 0;
}
CF850F Rainbow Balls
$m$ 表示球总数。
设 $a_{n,i}$ 为 $n$ 次操作后，第 $i$ 个颜色球的个数。
设 $f(x)$ 为有 $x$ 个球的颜色的势能函数，整个局面的势能函数为 $\Phi(A)=\sum f(a_{i})$。
注意到 $E(\Phi(A_{n+1})\mid A_0,A_1,\cdots,A_n)=E(\Phi(A_{n+1})\mid A_n)$，就等于
\[\sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\]为满足 $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有
\[\sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\left(\frac{a_{n,i}(m-a_{n,i})}{m(m-1)}f(a_{n,i}+1)+\frac{a_{n,i}(m-a_{n,i})}{m(m-1)}f(a_{n,i}-1)+(1-\frac{2a_{n,i}(m-a_{n,i})}{m(m-1)})f(a_{n,i})\right)\\ f(x)-\frac{x}{m}=\frac{x(m-x)}{m(m-1)}f(x+1)+\frac{x(m-x)}{m(m-1)}f(x-1)+\frac{2x^2-2mx-m+m^2}{m(m-1)}f(x)\\ f(x+1)=2f(x)-f(x-1)-\frac{m-1}{m-x}\]这东西不太好处理，差分一下 $g(x)=f(x)-f(x-1)$。
\[f(x+1)-2f(x)+f(x-1)=-\frac{m-1}{m-x}\\ g(x+1)-g(x)=-\frac{m-1}{m-x}\\ g(x+1)=g(x)-\frac{m-1}{m-x}\\ g(x)=g(0)-\sum\limits_{i=0}^{x-1}\frac{m-1}{m-i}\\ f(x)=f(0)+\sum\limits_{i=1}^xg(i)\\ f(x)=f(0)+\sum\limits_{i=1}^x(g(0)-\sum\limits_{j=0}^{i-1}\frac{m-1}{m-j})\\ f(x)=f(0)+xg(0)-\sum\limits_{i=1}^x\sum\limits_{j=0}^{i-1}\frac{m-1}{m-j}\\ f(x)=f(0)+xg(0)-\sum\limits_{j=0}^{x-1}(x-j)\frac{m-1}{m-j}\\ f(x)=f(0)+xg(0)-(m-1)\sum\limits_{j=0}^{x-1}(\frac{x-m}{m-j}-1)\\ f(x)=f(0)+xg(0)+(m-1)(m-x)\sum\limits_{j=0}^{x-1}\frac{1}{m-j}-x(m-1)\\\]取 $f(0)=0,g(0)=m-1$，则 $f(x)=(m-1)(m-x)\sum\limits_{i=0}^{x-1}\frac{1}{m-i}$。
设停时为 $t$，则 $\Phi(A_t)=f(m)+(n-1)f(0)=0$，为常数，所以 $E(t)=\Phi(A_0)-\Phi(A_t)$。
#include<cstdio>
int const mod=1e9+7;
int n,a[2510],f[100010],m,ans;
int pow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i),m+=a[i];
f[0]=0;
for(int i=1;i<=100000;i++)
f[i]=(f[i-1]+pow(m-i+1,mod-2))%mod;
for(int i=1;i<=100000;i++)
f[i]=1ll*(m-1)*(m-i)%mod*f[i]%mod;
for(int i=1;i<=n;i++)ans=(ans+f[a[i]])%mod;
printf("%d\n",ans);
return 0;
}
CF1349D Slime and Biscuits
设 $a_{n,i}$ 为 $n$ 步后第 $i$ 个人的饼干数量。
设 $f(x)$ 为有 $x$ 个饼干的人的势能函数，整个局面的势能函数为 $\Phi(A)=\sum f(a_{_i})$。
注意到 $E(\Phi(A_{n+1})\mid A_0,A_1,\cdots,A_n)=E(\Phi(A_{n+1})\mid A_n)$。
\[E(\Phi(A_{n+1})\mid A_n)=\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}}{m(n-1)}\left(f(a_{n,i}-1)+f(a_{n,j}+1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\\]为满足 $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有
\[\begin{aligned} \sum\limits_{k}f(a_{n,k})-1&=\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}}{m(n-1)}\left(f(a_{n,i}-1)+f(a_{n,j}+1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1&=\sum_i\left(\frac{a_{n,i}}{m}f(a_{n,i}-1)+\frac{m-a_{n,i}}{m(n-1)}f(a_{n,i}+1)+\frac{(m-a_{n,i})(n-2)}{m(n-1)}f(a_{n,i})\right)\\ f(x)-\frac{x}{m}&=\frac{x}{m}f(x-1)+\frac{m-x}{m(n-1)}f(x+1)+\frac{(m-x)(n-2)}{m(n-1)}f(x)\\ f(x+1)&=\left(\frac{m(n-1)}{m-x}-(n-2)\right)f(x)-\frac{(n-1)x}{m-x}f(x-1)-\frac{(n-1)x}{m-x} \end{aligned}\]将 $x=0$ 代入可得 $f(1)=f(0)$，所以取 $f(0)=f(1)=0$。
设停时为 $t$，则 $\Phi(A_t)=f(m)+(n-1)f(0)$，为常数，所以 $E(t)=\Phi(A_0)-\Phi(A_t)$。
#include<cstdio>
int const mod=998244353;
int pow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int f[300010],n,m,a[100010],ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i),m+=a[i];
for(int i=1;i<300000;i++){
f[i+1]=(1ll*m*(n-1)%mod*pow(m-i,mod-2)%mod-n+2ll+mod)%mod*f[i]%mod;
f[i+1]=(f[i+1]-1ll*(n-1)*i%mod*pow(m-i,mod-2)%mod*(f[i-1]+1)%mod+mod)%mod;
}
for(int i=1;i<=n;i++)ans=(ans+f[a[i]])%mod;
ans=(ans-f[m]+mod)%mod;
printf("%d\n",ans);
return 0;
}
CF1479E School Clubs
套路设出一个状态的势能函数 $\phi(A)$ 为每组的势能相加 $\sum f(a_i)$。
容易注意到 $f(0)=0$。
为满足$E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有
\[\phi(A_t)-1=\phi(A_{t+1})\\ \sum_i\frac {a_i}n(\frac 12(\phi(A_t)-f(a_i)+f(a_i-1)+f(1))+\frac{a_i}{2n}\phi(A_t)+\sum_{j\ne i}\frac {a_j}{2n}(\phi(A_t)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)))\\ -1=\sum_i\frac {a_i}{2n}(-f(a_i)+f(a_i-1)+f(1)+\sum_{j\ne i}\frac {a_j}{n}(-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)))\\ -1=-\sum_i\frac {a_i}{2n}f(a_i)+\sum_i\frac {a_i}{2n}f(a_i-1)+\sum_i\frac {a_i}{2n}f(1)-\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_i)-\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_j)+\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_i-1)+\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_j+1)\\\] \[-\sum_i\frac{a_i}n=\sum_i\frac {a_i}{2n}f(1)-\sum_i\frac {3na_i-2a^2_i}{2n^2}f(a_i)+\sum_i\frac {2na_i-a^2_i}{2n^2}f(a_i-1)+\sum_i\frac {na_i-a^2_i}{2n^2}f(a_i+1) \\ -\frac xn=\frac x{2n}f(1)-\frac{3nx-2x^2}{2n^2}f(x)+\frac{2nx-x^2}{2n^2}f(x-1)+\frac{nx-x^2}{2n^2}f(x+1)\\\]设 $f(1)=-2$。
\[0=-\frac{3nx-2x^2}{2n^2}f(x)+\frac{2nx-x^2}{2n^2}f(x-1)+\frac{nx-x^2}{2n^2}f(x+1)\\ f(x+1)=\frac {2n^2}{nx-x^2}(\frac{3nx-2x^2}{2n^2}f(x)-\frac{2nx-x^2}{2n^2}f(x-1))\\ f(x+1)=\frac{3n-2x}{n-x}f(x)-\frac{2n-x}{n-x}f(x-1)\\ f(x+1)=\frac{3n-2x}{n-x}\frac{d_1}{d_2}-\frac{2n-x}{n-x}\frac{s_1}{s_2}\\ f(x+1)=\frac{(3n-2x)d_1}{(n-x)d_2}-\frac{(2n-x)s_1}{(n-x)s_2}\\ f(x+1)=\frac{(3n-2x)d_1s_2-(2n-x)s_1d_2}{(n-x)d_2s_2}\]容易发现此时的 $E(A_t)=f(n)$ 为常数，答案即为 $\sum f(a_i)-f(n)$。
线性算即可，可以过，记得开 C++17(64)。
#include<cstdio>
#include<algorithm>
int const mod=998244353;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int n,m,a[1010];
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",a+i),n+=a[i];
std::sort(a+1,a+m+1);
int ans=0;
int s1=0,d1=mod-2,s2=1,d2=1,p1,p2,j=1;
while(j<=m&&a[j]==1)ans=(ans+mod-2)%mod,++j;
for(int i=1;i<n;i++){
p2=1ll*(n-i)*d2%mod*s2%mod;
p1=((3ll*n-2*i)*d1%mod*s2+(mod-1ll)*(2*n-i)%mod*s1%mod*d2)%mod;
while(j<=m&&a[j]==i+1)ans=(ans+1ll*p1*pow(p2,mod-2))%mod,++j;
s1=d1,s2=d2,d1=p1,d2=p2;
}
printf("%lld\n",(ans+(mod-1ll)*d1%mod*pow(d2,mod-2))%mod);
return 0;
}
CF 题解给出的做法是将下面的式子用多项式科技优化。
\[g(x)=f(x+1)-f(x)\\ g(x)=\frac{2n-x}{n-x}g(x-1)\\ g(x)=g(0)\prod_{i=1}^x\frac{2n-i}{n-i}\\ f(x)=-2\sum_{i=0}^{x-1}\prod_{j=1}^i\frac{2n-j}{n-j}\]