鞅
鞅最早指一种赌博策略，后被引进到了数学中，用来指一类随机过程。它有许多种不同程度的推广，这里义离散时间鞅为满足以下条件的随机过程（依赖于时间的随机变量序列） \(X_0,X_1,X_2,…\) 。
\(∀n∈N,E\ [X_n]<∞\)。
\(∀n∈N+,E\ [X_{n+1}∣X_n,X_{n−1},…,X_0]=X_n\)。
第一条比较平凡，第二条用比较通俗的语言讲，就是在已知之前的所有观测值的前提下，下一次观测值的期望等于这一次观测值。
同时有更为一般的定义，若：
\(∀n∈N,E\ [Y_n]<∞\)。
\(∀n∈N+,E\ [Y_{n+1}∣X_n,X_{n−1},…,X_0]=Y_n\) 。
则称随机过程 \(Y0,Y1,…\) 是关于另一随机过程 \(X0,X1,…\) 的鞅。
容易证明，对于任意 \(n∈N+,E\ [X_n]=X_0\)，也就是认为 \(X_0,X_1,…\) 是赌徒的财产，则无论赌多少次，赌徒最后的期望财产依旧等于他最开始的财产。
下面举几个鞅的例子：
设 \(X_n\) 表示一个赌徒抛掷了 \(n\) 次公平硬币（正反面概率相等）后的财产。规则是若为正面朝上，则获得 \(1\) 元；反之输掉 \(1\) 元。在已知过去所有时刻的财产下，若赌徒再抛掷一次硬币，显然抛掷完后财产的期望依旧等于现在的财产数量。故 \(X_0,X_1,X_2,…\) 这一随机过程是鞅。
接着上面的例子，设 \(Y_n=X^2_n−n\)，则 \(Y_0,Y_1,…\) 这一随机过程是关于随机过程 \(X_0,X_1,…\) 的鞅，证明如下：
\[E\ [Y_n+1]=\frac{(X_n−1)^2−(n+1)+(X_n+1)^2-(n+1)}{2}\\
=\frac{1}{2}(X^2_n−2X_n+1−n−1+X^2_n+2X_n+1−n−1)\\
=\frac{1}{2}(2X^2_n−2n)\\
=X^2_n−n\\
=Y_n
\]
注意到：
\[E\ [Y_n]=E\ [X^2_n]−n=E\ [X^2_0]
\]
取 \(X_0=0\) 则 \(E\ [X^2_n]=n\) ，如果 \(X_0≠0\) 只需要 \(Y_n\) 定义为 \((X_n−X_0)^2−n\) 即可。
这一例子可以表明赌徒的全部收益或损失大致在抛掷次数的正负平方根之间变化。
鞅的停时定理
对于一列随机变量 \(X_0,X_1,…\)，停时 \(τ\) 为一个随机变量，满足性质：对于任意时间 \(t\)，事件 \(τ=t\) 是否发生仅取决于 \(X_0,X_1,…\) 的取值。也就是说只根据现在获得的信息就可以知道是否已经停下，而不需要将来的信息。
随机时刻：
设随机变量 \(T\) , 如果 \(T∈N∪{+∞}\) , 且 \(T=n\) 的示性函数 \(I_{T=n}\) 为 \(X_0,X_1...,X_n\) 的函数，则称 \(T\) 为 \(X\) 的随机时刻.
停时 :
若 \(T\) 为 \(X\) 的随机时刻且 \(P(T<+∞)=1\) 则称 \(T\) 为 \(X\) 的停时。
停止过程:
若 \(T\) 为 \(X\) 的随机时刻。定义 \(X\) 的停止过程 \(\overline{X}\) 为
\[\overline{X}_n=
\begin{cases}
X_n\ (n≤T)\\
\\
X_T\ (n>T)
\end{cases}
\]
显然若 \(X\) 为鞅则 \(\overline{X}\) 为关于 \(X\) 的鞅。
停时定理：
若鞅 \(X\) 和停时 \(T\) 满足以下条件之一：
\(\overline{X}\) 都有界。
\(T\) 有界。
\(E\ (T)<+∞\) , 且 \(E\ (|X_n+1−X_n||X_0,...,X_n)\) 有界。
那么 \(E\ (X_T)=E\ (X_0)\)
套路：
构造势函数 \(ϕ(X)\) , 使得 \(E(ϕ(X_{n+1})|X_0,...,X_n)=ϕ(X_n)+1\)。
这样的话 \(ϕ(X_n)−n\) 就是一个鞅。
利用停时定理有：
\[E(ϕ(X_T)−T)=E(ϕ(X_0))=E(ϕ(X_T))−E(T)
\]
即：
\[E(T)=E(ϕ(X_T))−E(ϕ(X_0))
\]
这样求出 \(E(ϕ(X_0))\) 和 \(E(ϕ(X_T))\) 就可以求出 \(E(T)\) 了。
例题
#88. 战争
我们设 \(ϕ(X)=\sum f(a_{i})\) ，列方程：
\[E(ϕ(X_{n+1}))=ϕ(X_n)+1
\]
\[ϕ(X_{n+1})-ϕ(X_n)=1
\]
假如发生冲突的是 \(i\) 国家和 \(j\) 国家：
\[p\times (f(a_i+1)+(a_j-1)\times f(1))+p\times (f(a_j+1)+(a_i-1)\times f(1))+(1-2p)\times (a_i+a_j)\times f(1)-f(a_i)-f(a_j)=1
\]
令 \(f(1)=0\) 式子会简洁很多
\[p\times f(a_i+1)+p\times f(a_j+1)-f(a_i)-f(a_j)=1
\]
我们只需让 \(∀a\)，有 \(p\times f(a+1)-f(a)=\frac{1}{2}\) 即可。
对于 \(f(n)=k\times f(n-1)+b\) 形式的递归式，可以设 \(f(n)+c=k\times (f(n-1)+c)\) ，解出 \(c\) ，剩余的部分是一个等比数列。
本题中 \(c=\frac{1}{2(p-1)}\) ，进而 \(f(n)=(p^{1-n}+1)\times \frac{1}{2(p-1)}\) 。
因此我们可以方便的计算 \(E(X_T)\) 和 \(E(X_0)\) ，输出 \(E(X_T)-E(X_i)\) 即可。
点击查看代码
#include
using namespace std;
const int p=1e9+7,inv2=(p+1)/2;
int a[40000005],pw0[65537],pw1[65537];
int pw(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%p;
x=1ll*x*x%p;y>>=1;
}
return res;
}
int mod(int x){return x>=p?x-p:x;}
unsigned long long x,y,z,b1,b2;
void prework(){
int m,q=0,now=1;unsigned long long l,r,tmp;
scanf("%d%llu%llu%llu%llu%llu",&m,&x,&y,&z,&b1,&b2);
while(m--){
scanf("%d%llu%llu",&q,&l,&r);
r=r-l+1;
while(now<=q)a[now]=(b1%r+l)%(p-1),tmp=x*b2+y*b1+z,b1=b2,b2=tmp,now++;
}
}
int pw2(int x){return 1ll*pw0[x&65535]*pw1[x>>16]%p;}
int main(){
int type,n,s,t,r,x0=0;long long x;
scanf("%d%d%d%d",&type,&n,&s,&t);
t=1ll*s*pw(t,p-2)%p;r=pw(mod(2*t-2),p-2);
if(!type)for(int i=1;i<=n;i++)scanf("%lld",&x),a[i]=x%(p-1);
else prework();
s=0;
int ti=pw(t,p-2);
pw0[0]=pw1[0]=1;
for(int i=1;i<=65536;i++)pw0[i]=1ll*pw0[i-1]*ti%p;
for(int i=1;i<=65535;i++)pw1[i]=1ll*pw1[i-1]*pw0[65536]%p;
for(int i=1;i<=n;i++){
s=(s+a[i])%(p-1);
x0=mod(x0+pw2(a[i]+p-2)-1);
}
printf("%lld",1ll*(x0-pw(t,p-s)+1+p)*r%p);
return 0;
}
CF1025G Company Acquisitions
设 \(f(x)\) 为被选中点后面跟随 \(x\) 个未被选中点的势能，设 \(ϕ(A)\) 表示整个局面的势能。
列方程：
\[E(ϕ(X_{n+1}))=ϕ(X_n)+1
\]
\[ϕ(X_{n+1})-ϕ(X_n)=1
\]
设被选中的两个点后面分别跟随着的点的数量为 \(a\) 和 \(b\) ，有：
\[\frac{1}{2}(f(a+1)+bf(0))+\frac{1}{2}(af(0)+f(b+1))-f(a)-f(b)=1
\]
令 \(f(0)=0\) 有：
\[\frac{1}{2}f(a+1)+\frac{1}{2}f(b+1)-f(a)-f(b)=1\\
f(a+1)+f(b+1)=2f(a)+2f(b)+2\\
\]
不妨令 ：
\[f(a+1)=2f(a)+1\\
\\
f(b+1)=2f(b)+1\\
\]
也就是：
\[f(x)=2^x-1
\]
令初始时节点 \(i\) 后面跟着的节点数为 \(a_i\) ，有：
\[T=E(ϕ(T))-E(ϕ(0))=(2^{n-1}-1)-\sum(2^{a_i}-1)
\]
点击查看代码
#include
using namespace std;
const int md=1e9+7;
inline int pwr(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%md;
x=1ll*x*x%md;y>>=1;
}
return res;
}
int n,a[505];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
a[x]++;
}
int res=(pwr(2,n-1)-1+md)%md;
for(int i=1;i<=n;i++){
if(a[i])res=(res-pwr(2,a[i])+1+md)%md;
}
printf("%d\n",res);
return 0;
}
CF850F Rainbow Balls
考虑枚举一下球的颜色，将所有球分成两类，是这种颜色的与不是这种颜色的，设 \(f(x)\) 为有 \(x\) 个这种颜色的球的势能，设 \(ϕ(A)\) 表示整个局面的势能。
令 \(m=\sum_{i=1}^n a_i\) ，有：
\[\sum\frac{a_i\times (a_i-1)+(m-x)\times (m-a_i-1)}{m\times(m-1)}f(a_i)+\frac{a_i\times(m-a_i)}{m\times(m-1)}(f(a_i+1)+f(a_i-1))-f(a_i)=1
\]
化简：
\[\sum_{i=1}^n\frac{2a_i^2+m^2-2ma_i-m}{m^2-m}f(a_i)+\frac{a_im-a_i^2}{m^2-m}(f(a_i+1)+f(a_i-1))-f(a_i)=1\\
\sum_{i=1}^n\frac{2a_i^2-2ma_i}{m^2-m}f(x)+\frac{a_im-a_i^2}{m^2-m}(f(a_i+1)+f(a_i-1))=1\\
\sum_{i=1}^n\frac{a_im-a_i^2}{m^2-m}(f(a_i+1)+f(a_i-1)-2f(a_i))=1\\
\sum_{i=1}^n\frac{a_i(m-a_i)}{m(m-1)}(f(a_i+1)+f(a_i-1)-2f(a_i))=1\\
\]
由于 \(\sum_{i=1}^n\frac{a_i}{m}=1\) ，我们想让上式成立只需：
\[\frac{m-a_i}{m-1}(f(a_i+1)+f(a_i-1)-2f(a_i))=1
\]
也就是：
\[f(i+1)+f(i-1)-2f(i)=\frac{m-1}{m-i}
\]
令 \(g(i)=f(i)-f(i-1)\) ，有：
\[g(i+1)-g(i)=\frac{m-1}{m-i}
\]
我们可以递推出 \(g(i)\)，然后递推出 \(f(i)\)，但是直接递推出终状态的势能是 \(O(m)\) 的，我们看能不能快速计算：
\[\phi(A_t)=\sum_{i=0}^{m-1}\sum_{j=0}^{i}\frac{m-1}{m-j}=\sum_{j=0}^{m-1}(m-j)\cdot\frac{m-1}{m-j}=m(m-1)
\]
时间复杂度 \(O(\max a_i\log n)\) 。
点击查看代码
#include
using namespace std;
int n,m,lim;
int a[2505],g[100005],f[100005];
const int md=1e9+7;
inline int pwr(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%md;
x=1ll*x*x%md;y>>=1;
}
return res;
}
inline void init(){
for(int i=1;i<=lim;i++)g[i]=(g[i-1]+1ll*(m-1)*pwr(m-i+1,md-2))%md;
for(int i=1;i<=lim;i++)f[i]=(f[i-1]+g[i])%md;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
lim=max(lim,a[i]);m=(m+a[i])%md;
}
init();
int res=1ll*m*(m-1)%md;
for(int i=1;i<=n;i++)res=(res-f[a[i]]+md)%md;
printf("%d\n",res);
return 0;
}
CF1479E School Clubs
类似上一题列式子的方法，可以推出：
\[-\frac{x}{n}=\frac{x}{2n}f(1)+\frac{2x^2-3nx}{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\)，可以消去常数项，然后写成递推式的形式：
\[f(x+1)=\frac{3n-2n}{n-x}f(x)-\frac{x-2n}{n-x}f(x-1)
\]
这样就可以 \(O(n)\) 地解决了，线性算即可，可以过 。
点击查看代码
#include
using namespace std;
int const md=998244353;
int pwr(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%md;
x=1ll*x*x%md,y>>=1;
}
return res;
}
int n,m,a[1005];
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",a+i),n+=a[i];
sort(a+1,a+m+1);
int ans=0;
int s1=0,d1=md-2,s2=1,d2=1,p1,p2,j=1;
while(j<=m&&a[j]==1)ans=(ans+md-2)%md,++j;
for(int i=1;i p2=1ll*(n-i)*d2%md*s2%md; p1=((3ll*n-2*i)*d1%md*s2+(md-1ll)*(2*n-i)%md*s1%md*d2)%md; while(j<=m&&a[j]==i+1)ans=(ans+1ll*p1*pwr(p2,md-2))%md,++j; s1=d1,s2=d2,d1=p1,d2=p2; } printf("%lld\n",(ans+(md-1ll)*d1%md*pwr(d2,md-2))%md); return 0; }