前言

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

鞅的停时定理

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

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

• $E(X_t)<\mathrm{\infty },\mathrm{\forall }t\ge 0$
• $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 \mathrm{\infty }$ 有限：$\mid a\mid <\mathrm{\infty }$；
• $a\in R\cup \mathrm{\infty }$ 有界：$\mathrm{\exists }l,r\in R,a\in [l,r]$；
• $a_i\in R\cup \mathrm{\infty }$ 一致有界：$\mathrm{\forall }i,\mathrm{\exists }l,r\in R,a_i\in [l,r]$；
• 事件 $A$ 几乎必然发生：$P(A)=1$。

势能函数

对于随机时间序列 $A_0,A_1,\cdots$，$t$ 为其停时，终止状态为 $A_t$，求 $E(t)$。

构造势能函数 $\mathrm{\Phi }(A)$，满足：

• $E(\mathrm{\Phi }(A_{n+1})-\mathrm{\Phi }(A_n)\mid A_0,A_1,\cdots ,A_n)=-1$；
• $\mathrm{\Phi }(A_t)$ 为常数。

构造序列 $X_i=\mathrm{\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(\mathrm{\Phi }(A_0))-\mathrm{\Phi }(A_t)$。

CF1479E School Clubs

题意

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

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

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

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

$n\le 4\times {10}^8$

思路

设 $\varphi (A)$ 为状态 $A$ 的势能，构造使得 $\varphi (A_t)-1=\varphi (A_{t+1})$，设 $f(x)$ 为学生数量为 $x$ 的组的势能函数，则有： $$\begin{array}{rl}\varphi (A_t)-1& =\varphi (A_{t+1})\\ \varphi (A_t)-1& =\sum _i\frac{a_i}{n}(\frac{1}{2}(\varphi (A_t)-f(a_i)+f(a_i-1)+f(1))+\frac{a_i}{2n}\varphi (A_t)+\sum _{j\ne i}\frac{a_j}{2n}(\varphi (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{3n{a}_i-2a_i^2}{2n^2}f(a_i)+\sum _i\frac{2n{a}_i-a_i^2}{2n^2}f(a_i-1)+\sum _i\frac{n{a}_i-a_i^2}{2n^2}f(a_i+1)\\ -\frac{x}{n}& =\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{array}$$

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#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;
}