MENU

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
Last Modified: May 22, 2024
Archives Tip
QR Code for this page
Tipping QR Code