前言

该内容算法竞赛涉及不多，属于较深概率论内容。

鞅的停时定理

“鞅”，martingale 用来指一类随机过程，定义如下：

鞅是一种离散时间的随机过程 \(X_0,X_1,\cdots\) 满足：

\(E(X_t)<\infty,\forall t\geq0\)

\(E(X_{t+1}\mid X_0,\cdots X_t)=X_t\)

根据定义可以得到 \(E(X_t)=X_0\)。

停时定理

设 \(t\) 为鞅过程 \({X_0,X_1,\cdots}\) 的停时，当下面三个条件之一成立时，有 \(E(X_t)=X_0\)：

\(t\) 几乎必然有界；
\(\mid X_{i+1}-X_i\mid\) 一致有界，\(E(t)\) 有限；
\(X_i\) 一致有界，\(t\) 几乎必然有限。

名词解释：

\(a\in R\cup{\infty}\) 有限：\(\mid a\mid <\infty\)；
\(a\in R\cup{\infty}\) 有界：\(\exists l,r\in R,a\in[l,r]\)；
\(a_i\in R\cup{\infty}\) 一致有界：\(\forall i,\exists l,r\in 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)\) 为常数。

构造序列 \(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)\)。

CF1479E School Clubs

题意

有 \(n\) 个学生和 \(m\) 个组，每个人在一个组里面，第 \(i\) 个组的人数为 \(a_i\)。

现在，每天有一个学生（\(n\) 个学生中随机的一个）会：

有一半的概率他会脱离这个组，并且成立一个新的组。
有一半的概率他会脱离这个组，并且进入一个已经成立的组。他进入第 \(i\) 个组的概率为 \(\frac {a_i} n\)，他可能会回到原来的组。

求第一次出现所有学生在同一个组的期望天数，对 \(998244353\) 取模。

\(n\leq 4\times10^8\)

思路

设 \(\phi(A)\) 为状态 \(A\) 的势能，构造使得 \(\phi(A_t)-1=\phi(A_{t+1})\)，设 \(f(x)\) 为学生数量为 \(x\) 的组的势能函数，则有： \[ \begin{aligned}\phi(A_t)-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)\\ \end{aligned} \]

因为我们需要的只是初始状态与停时的势能差，那么将势能具体设为什么都无所谓，所以为了消去常数项我们可以设 \(f(1)=-2\)，则： \[ \begin{aligned}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)\\ \end{aligned} \]

发现 \(\phi(A_t)=f(n)\) （表示局面为只有一个人数为 \(n\) 的组）是个常数（知道 \(f(0)\) 和 \(f(1)\) 可以被表示），那么可以用停时定理。

观察数据范围发现没法存下线性求逆元，也没法每次快速幂求。那怎么办呢？

官方题解的做法将 \(f\) 进行差分然后利用快速阶乘算法计算，即： \[ \begin{aligned}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} \end{aligned} \]

实际上我们可以直接对对于这个式子 \(f(x+1)=\frac{3n-2x}{n-x}f(x)-\frac{2n-x}{n-x}f(x-1)\) 线性递推。因为我们要求的是 \(E(\phi(A_t))\) 和 \(\phi(A_0)=\sum_if(a_i)\)，所以我们只在算 \(m\) 个 \(f(a_i)\) 和 \(f(n)\) 的时候快速幂，递推的时候分别维护分子和分母即可。如果你拥有优秀的常数即可通过。

代码

#include<cstdio>
#include<algorithm>
inline int read(){
	int x=0,w=0;char c=getchar();
	while(!isdigit(c)) w|=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
const int mod=998244353;
inline int pow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod; return ans;}
int n,m,a[1010];
signed main(){
	m=read();
	for(int i=1;i<=m;i++) n+=a[i]=read();
	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)*(2ll*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;
}