鞅、停时定理与势能函数

· · 算法·理论

本篇博客全篇参考 \color{black}{g}{\color{red} xy001} 巨佬的博客，并在他的指导下完成，在这里感谢并orz！

离散时间鞅

定义离散时间鞅为一个时间离散的随机过程 \{X_0,X_1,\cdots\} ，使得 \forall n\in \N 均满足：

停时定理

设 t 为鞅过程 \{X_0,X_1,\cdots\} 的停时，当满足以下任意一个条件时，有 E(X_t)=X_0

解释：

势能函数

设 t 为时间序列 \{A_0,A_1\cdots\} 的停时，求 E(t)

构造势能函数 \phi(A) 满足

构造序列 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+\phi(A_t))=E(\phi(A_0))\Rightarrow E(t)=E(\phi(A_0))-\phi(A_t)

例题：

CF1349D Slime and Biscuits

设 f(x) 表示有 x 个饼干的人的势能函数，整个局面的势能函数 \phi(A) 为 \sum f(x)，以下的 a_i 表示当前局面第 i 个人的饼干数。

因为 E(X_{n+1}|X_0,X_1\cdots X_n)=E(X_{n+1}|X_n)，所以有

\begin{aligned} &\phi(A_n)-1=\phi(A_{n+1})\\ &\phi(A_n)-1=\sum_i\frac{a_i}{m}\sum_{j\neq i}\frac{1}{n-1}(\phi(A_n)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1))\\ &-1=\sum_i\frac{a_i}{m}\sum_{j\neq i}\frac{1}{n-1}(-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1))\\ &-1=\sum_i\frac{a_i}{m}(-f(a_i)+f(a_i-1))+\sum_{j}\frac{1}{n-1}(-f(a_j)+f(a_j+1))\sum_{i\neq j}\frac{a_i}{m}\\ &-1=\sum_i\frac{a_i}{m}(-f(a_i)+f(a_i-1))+\sum_{i}\frac{m-a_i}{(n-1)m}(-f(a_i)+f(a_i+1))\\ &-\sum_i\frac{a_i}{m}=\sum_i\frac{a_i}{m}(-f(a_i)+f(a_i-1))+\frac{m-a_i}{(n-1)m}(-f(a_i)+f(a_i+1)) \end{aligned}

设 x=a_i

-x=-xf(x)+xf(x-1)-\frac{m-x}{n-1}f(x)+\frac{m-x}{n-1}f(x+1)\\ f(x+1)=-\frac{x(n-1)}{m-x}+(\frac{x(n-1)}{m-x}+1)f(x)-\frac{x(n-1)}{m-x}f(x-1)

将 x=0 代入得 f(1)=f(0)。设 f(1)=f(0)=0，此时 \phi(A_t)=f(m)-(n-1)f(0) 为一个常数，E(t)=E(\phi(A_0))-\phi(A_t)=\sum f(a_i)-f(m)。事实上，只要使 \phi(A_t) 为常数，f(0) 可以为任何数。

#include<bits/stdc++.h>
using namespace std;
namespace FGF
{
    int n,m,ans;
    const int N=3e5+5,mo=998244353;
    int a[N],f[N],inv[N];
    void work()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)   
            scanf("%d",&a[i]),m+=a[i];
        inv[1]=1;
        for(int i=2;i<=m;i++)
            inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
        for(long long i=1,y;i<m;i++)
            y=i*(n-1)%mo*inv[m-i]%mo,f[i+1]=(((y+1)%mo*f[i]%mo-y*(f[i-1]+1)%mo)%mo+mo)%mo;
        for(int i=1;i<=n;i++)
            ans=(ans+f[a[i]])%mo;
        printf("%d\n",(ans-f[m]+mo)%mo);
    }
}
int main()
{
    FGF::work();
    return 0;
}

CF1025G Company Acquisitions

这题题意太阴间了吧！

设 f(x) 表示有 x 个叶子节点的菊花的势能函数，整个局面的势能函数 \phi(A) 为 \sum f(x)，以下的 a_i 表示当前局面第 i 个菊花的叶子节点个数。

因为 E(X_{n+1}|X_0,X_1\cdots X_n)=E(X_{n+1}|X_n),\phi(A_n)-1=\phi(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)+xf(0))\\ f(x+1)=2f(x)-1-xf(0)

取 f(0)=0，则有 \phi(A_t)=f(n-1)=1-2^{n-1} 为常数，E(t)=E(\phi(A_0))-\phi(A_t)=\sum f(cnt_i)-f(n-1)

#include<bits/stdc++.h>
using namespace std;
namespace FGF
{
    int n;
    const int N=505;
    const int mo=1e9+7;
    int cnt[N],pw[N],ans;
    void work()
    {
        scanf("%d",&n);
        pw[0]=1;
        for(int i=1;i<=n;i++)
            pw[i]=pw[i-1]*2%mo;
        for(int i=1,x;i<=n;i++)
        {
            scanf("%d",&x);
            if(~x)cnt[x]++;
        }
        for(int i=1;i<=n;i++)
            ans=(ans+1-pw[cnt[i]]+mo)%mo;
        ans=(ans+pw[n-1]-1)%mo;
        printf("%d\n",ans);
    }
}
int main()
{
    FGF::work();
    return 0;
}

CF850F Rainbow Balls

设 f(x) 表示有 x 个球的颜色的势能函数，整个局面的势能函数 \phi(A) 为 \sum f(x)，以下的 a_i 表示当前局面第 i 个颜色的球数，m 表示总球数。

因为 E(X_{n+1}|X_0,X_1\cdots X_n)=E(X_{n+1}|X_n)，所以有

\phi(A_n)-1=\phi(A_{n+1})\\ \phi(A_n)-1=\frac{1}{m(m-1)}\left(\sum_ia_i(a_i-1)\phi(A_n)+\sum_i\sum_{j\neq i}a_ia_j(\phi(A_n)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1))\right)\\ -1=\frac{1}{m(m-1)}\left(\sum_i\sum_{j\neq i}a_ia_j(-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1))\right)\\ -1=\frac{1}{m(m-1)}\sum_ia_i(m-a_i)(f(a_i-1)-2f(a_i)+f(a_i+1))\\ 0=m+\frac{1}{(m-1)}\sum_ia_i(m-a_i)(f(a_i-1)-2f(a_i)+f(a_i+1))\\ 0=\sum_ia_i(1+\frac{m-a_i}{m-1}(f(a_i-1)-2f(a_i)+f(a_i+1)))\\

上式恒成立，将 x=a_i 代入得

0=x(1+\frac{m-x}{m-1}(f(x-1)-2f(x)+f(x+1)))\\ \frac{m-1}{x-m}+f(x)-f(x-1)=f(x+1)-f(x)

设 g(x)=f(x)-f(x-1)，则有

\begin{aligned} g(x+1)&=g(x)+\frac{m-1}{x-m}\Rightarrow g(x)=g(0)+\sum_{i=0}^{x-1}\frac{m-1}{i-m}\\ f(x)&=f(0)+\sum_{i=1}^xg(i)\\ &=f(0)+\sum_{i=1}^x(g(0)+\sum_{j=0}^{i-1}\frac{m-1}{j-m})\\ &=f(0)+xg(0)+\sum_{i=1}^x\sum_{j=0}^{i-1}\frac{m-1}{j-m}\\ &=f(0)+xg(0)+(m-1)\sum_{j=0}^{x-1}\frac{x-j}{j-m}\\ &=f(0)+xg(0)-(m-1)\sum_{j=0}^{x-1}(\frac{m-x}{j-m}+1)\\ &=f(0)+xg(0)+(m-1)(m-x)\sum_{j=0}^{x-1}\frac{1}{m-j}-x(m-1)\\ \end{aligned}

取 f(0)=0,g(0)=m-1，此时 \phi(A_t)=f(m)=0 为一个常数，E(t)=E(\phi(A_0))-\phi(A_t)=\sum f(a_i)

#include<bits/stdc++.h>
using namespace std;
namespace FGF
{
    const int N=1e5+5,mo=1e9+7;
    int a[N],n,f[N],sum[N],m,ans,mx;
    int qpow(int x,int y)
    {
        int s=1;
        while(y)
        {
            if(y&1)s=1ll*s*x%mo;
            x=1ll*x*x%mo;
            y>>=1;
        }
        return s;
    }
    void work()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),m+=a[i],mx=max(mx,a[i]);
        for(int i=1;i<=mx;i++)
            sum[i]=(sum[i-1]+qpow(m-i+1,mo-2))%mo;
        for(int i=1;i<=mx;i++)
            f[i]=1ll*(m-1)*(m-i)%mo*sum[i]%mo;
        for(int i=1;i<=n;i++)
            ans=(ans+f[a[i]])%mo;
        printf("%d\n",ans);
    }   
}
int main()
{
    FGF::work();
    return 0;
}