Solution. CF1025G Company Acquisitions

Description

有 $n$ 个结点，每个结点有两种状态：active 和 acquired。

一个 active 结点后面跟着若干 acquired 结点。

对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。

每次随机选择两个 active 结点，随机让其中一个收购另一个。

求只剩一个 active 结点的期望步数。

$n\le 500$

Solution

这里有一些关于鞅和停时定理的理解，我也不知道对不对，可供参考。

使用势能法。

对于一个局面 $X$，设 active 结点数量为 $k$，将操作视作先随机选择 $A$，再随机选择 $B$，让 $A$ 收购 $B$。

设第 $i$ 个 active 结点后跟着 $a_i$ 个 acquired 结点，设势能函数为：
$$
\Phi(X)=\sum_{i=1}^k f(a_i)
$$
我们希望每次操作使得势能期望 $-1$，于是有：
$$
\sum_{i=1}^kf(a_i)=\sum_{i=1}^k \frac1k\left(a_if(0)+1+\sum_{j\ne i}\left(\frac1{k-1}f(a_j+1)+\frac{k-2}{k-1}f(a_j)\right)\right)
$$
调整求和顺序：
$$
\sum_{i=1}^kf(a_i)=\sum_{i=1}^k\left(\frac1ka_if(0)+\frac1k+\frac1kf(a_i+1)+\frac{k-2}{k}f(a_i)\right)
$$
考虑直接让 $f(a)$ 等于求和符号里那一串东西，化简得：
$$
\frac1kaf(0)+\frac1k+\frac1kf(a+1)-\frac2kf(a)=0
$$
发现烦人的 $k$ 可以扔掉：
$$
af(0)+1+f(a+1)-2f(a)=0
$$
考虑令 $f(0)=0$，可以进一步化简为：
$$
f(a+1)-2f(a)+1=0
$$
不难发现 $f(a)=-2^a+1$。

同时很显然，终止状态的势能唯一且达到最小值，可以使用鞅和停时定理那一套东西。

起始状态的势能减去终止状态的势能即可。

Code

namespace Main{
    const int N = 505;
    const int MOD = 1e9 + 7;
    int n, a[N], cnt[N];
    ll qpow(ll n, ll k){
        ll res = 1;
        while(k > 0){
            if(k & 1) res = res * n % MOD;
            n = n * n % MOD;
            k >>= 1;
        }
        return res;
    }
    void Main(){
        input(n);
        for(int i = 1; i <= n; i++){
            input(a[i]);
            if(a[i] != -1) cnt[a[i]]++;
        }
        ll ans = 0;
        for(int i = 1; i <= n; i++) ans = (ans - qpow(2, cnt[i]) + 1 + MOD) % MOD;
        write((ans + qpow(2, n - 1) - 1) % MOD);
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。