Solution. CF1951G Clacking Balls

Description

有 $m$ 个篮子放在一个环上，篮子按顺时针顺序编号为 $1\sim m$。有 $n$ 个球，第 $i$ 个球放在篮子 $a_i$ 中，$a_i$ 互不相同。接下来反复进行如下操作：从 $1\sim n$ 中等概率选出一个数 $i$，若球 $i$ 已被扔掉则什么都不做；否则将球 $i$ 移动到顺时针方向的下一个篮子里，如果下一个篮子里本来有一个球 $j$，则将球 $j$ 扔掉。进行一次上述操作总是花费 $1$ 单位时间，所有篮子中只剩下一个球时结束此过程。求过程持续的期望时间，答案对 $10^9 + 7$ 取模。

$1\le n\le 3\times 10^5, n\le m\le 10^9$

Solution

对于这种两个元素相遇后就发生合并或删除其中一个元素的问题，我们可以对相邻两个元素 $i - 1, i$ 进行考虑。原因在于，无论是有元素撞上了 $i - 1$ 还是 $i$ 撞上了其他元素，我们总是可以认为留下的元素仍然是 $i - 1$ 或 $i$，从而我们关注的两个元素的位置不受影响。

本题也可以运用这种思路。可以发现，最后留在场上球是球 $i$ 当且仅当在 $i - 1$ 追上 $i$ 之前，$i$ 就追上了 $i - 1$，这里说的追上指从顺时针方向追上。设 $p_i$ 表示 $i$ 追上 $i - 1$ 的概率，$e_i$ 表示 $i$ 追上 $i - 1$ 的期望步数，答案可以表示为 $\sum_i p_i e_i$。

我们首先考虑计算 $p_i$，显然这个值应当只与 $i - 1$ 与 $i$ 之间的距离有关。注意以下所说距离指的都是 $i - 1$ 沿顺时针方向走到 $i$ 的距离。

设 $P(d)$ 表示 $i - 1$ 与 $i$ 距离为 $d$ 时，$i$ 追上 $i - 1$ 的概率，容易写出方程：
$$
P(d)=\frac12 P(d - 1)+\frac12 P(d + 1)
$$
移项并重新整理即得：
$$
P(d)=2P(d - 1)-P(d-2)
$$
边界为 $P(0)=0,P(m)=1$。

处理这种递推式常见的手段是设 $P(1)=x$，将 $P(m)$ 表示为 $ax+b$ 的形式，然后解出 $x$ 的值。本题中 $m$ 的值域很大，没法直接递推，我们应当可以使用矩乘优化，不过此处 $P$ 的通项非常简单，我们很容易算出 $P(d)=\frac dm$。

接下来我们还需要知道 $e_i$。此处我选择了直接计算 $p_i e_i$ 的值。

设 $F(d)$ 表示 $i - 1$ 与 $i$ 距离为 $d$ 时，所有可能的小球移动过程中，$i$ 追上 $i - 1$ 的概率乘时间之和。这相当于设计一个随机过程，只要 $i - 1$ 和 $i$ 相遇就结束，然后从这个随机过程的期望持续时间中去掉 $i - 1$ 先追上 $i$ 的部分。

也可以写出关于 $F(d)$ 的方程：
$$
F(d)=\frac 12 F(d - 1)+\frac 12 F(d + 1) + \frac dm
$$
这里加上 $\frac dm$ 而不是 $1$ 是因为 $i$ 先追上 $i - 1$ 的概率是 $\frac dm$，只有这些情况会计入最终计算的值。

进行类似的移项与整理：
$$
F(d)=2F(d - 1)-F(d - 2)-\frac{2(d - 1)}{m}
$$
边界为 $F(0)=0,F(m)=0$。

可以设 $F(1)=x$ 然后手算找找规律，可以发现 $[x]F(d)=d$，这部分和 $P$ 是一样的。

$[x^0]F(d)$ 分子上的部分为 A007290，这使用数学手段应当也很容易推出。

总之我们有 $F(d)=dx-\frac{2\binom {d + 1}{3}}{m}$，令 $d=m$ 可以解出 $x=\frac{2\binom{m + 1}{3}}{m^2}$，于是 $F(d)$ 也就容易计算了。

最终的答案即为 $\sum_iF(a_i - a_{i - 1})$。

Code

namespace Main{
    const int MOD = 1e9 + 7;
    const int N = 300005;
    int t, n, m, a[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(t);
        while(t--){
            input(n, m);
            for(int i = 1; i <= n; i++) input(a[i]);
            sort(a + 1, a + n + 1);
            ll x = 2ll * (m + 1) * m % MOD * (m - 1) % MOD * qpow(6ll * m % MOD * m % MOD, MOD - 2) % MOD;
            ll ans = 0;
            a[n + 1] = m + a[1];
            for(int i = 1; i <= n; i++){
                ll d = a[i + 1] - a[i];
                ans = (ans + d * x % MOD - (d + 1) * d % MOD * (d - 1) % MOD * qpow(3ll * m % MOD, MOD - 2) % MOD + MOD) % MOD;
            }
            ans = ans * n % MOD * qpow(2, MOD - 2) % MOD;
            write(ans), puts("");
        }
        return;
    }
} // namespace Main

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

Catalog

Solution. CF1951G Clacking Balls

Description

Solution

Code