CF850F 题解

· · 题解

这篇题解大概讲的是本题势能函数做法的合法性。

部分节选自我关于停时和鞅的学习笔记

势能函数方法及其适用范围

对于随机事件序列 \{A_0,A_1,\cdots,A_{\tau}\}，\tau 为其停时，终止状态为 A_{\tau}，而我们希望求得 \mathbb E[\tau].

我们可以构造势能函数 \Phi(A)，满足：

设随机变量 X_n = \Phi(A_n) + n，则随机过程（即随机变量序列）\{X_0,X_1,\cdots,X_{\tau}\} 是个离散时间鞅（即满足所有随机变量有限且 \mathbb E[X_{n+1}\mid X_0,X_1,\cdots,X_n] = X_n 的随机过程）。

由 \Phi(A) = \Phi(A_{\tau}) 当且仅当 A = A_{\tau} 我们可以推得 \tau 也为 \{X_0,X_1,\cdots,X_{\tau}\} 的停时。

而可选停时定理指出：对一个离散时间鞅 \{X_0,X_1,\cdots,X_{\tau}\}，其停时为 \tau，若满足 X_n 一致有界，且 \tau 几乎必然有限（事实上停时定理有三种条件，但似乎 OI 中最常用的是这种），则 \mathbb E[X_{\tau}] = \mathbb E[X_0].

所以我们有：

\mathbb E[X_{\tau}] =\mathbb E[X_0] \Rightarrow \mathbb E[\Phi(A_0)] - \Phi(A_{\tau}) = \mathbb E [\tau]

回到本题

我们考虑类似地写出 \Phi(A) = \sum f(a_i)，f(a) 需要满足的条件：

\sum_i f(a_i) - 1

应与下式相等：

\sum_i \frac 1{m^{\underline 2}}((a_i^{\underline 2} + (m-a_i)^{\underline 2})f(a_i) + a_i(m-a_i)(f(a_i - 1) + f(a_i + 1)))

把右边的 f(a_i) 移过来，再展开一下式子可以得到：

\sum_i \frac {a_i}{m^{\underline 2}}((a_i-m)2f(a_i) + (m-a_i)(f(a_i - 1) + f(a_i + 1))) = -1

（我们有下降幂的完全平方公式 (x-y)^{\underline 2} = x^{\underline 2} - 2xy + (-y)^{\underline 2}）

\sum_i \frac {a_i(m-a_i)}{m^{\underline 2}}(f(a_i - 1) - 2f(a_i) + f(a_i + 1)) = -1

发现这个形式神似二维差分，于是我们设 g(x) = f(x + 1) - f(x).

\sum_i \frac {a_i(m-a_i)}{m^{\underline 2}}(g(a_i) - g(a_i - 1)) = -1

经验表明，对于要将所有元素集中在一个集合的这类问题，我们可能可以以正比于某个集合的大小的期望减少这个集合的势能。

即：

\frac {a(m-a)}{m^{\underline 2}}(g(a) - g(a - 1)) + \frac am = 0 g(a) - g(a - 1) = \frac{m-1}{a-m} < 0

容易发现，这样设置总能满足 \mathbb E[\Delta \Phi(A)] = -1 的条件，并且在本题中差分单调递减，又由于 \sum a_i 不变，可以看作一个经典的背包模型，势能的最低点必然是把一个函数取完而其它不取。

于是我们证明了 \Phi(A) = \Phi(A_{\tau})\Rightarrow A = A_{\tau}.

不妨设 f(0) = 0, g(0) = -\frac{m-1}{m}（容易发现，我们几乎可以随意给 g(0) 定一个值，只需要其满足 \Phi(A) = \Phi(A_{\tau})\Rightarrow A = A_{\tau}）

然后问题在于求 f(m)（f(a_i) 可以直接递推求）：

f(m) = \sum_{i=0}^{m-1}\sum_{j=0}^{i} \frac{m-1}{j-m} = \sum_{j=0}^{m-1}(m-j) \frac{m-1}{j-m} = -m(m-1)

于是这道题就做完了。

时间复杂度 \mathcal O(n + \max a_i).

代码

（我写的较丑，多了个 \log）

const int kN = 5e5 + 5;
const ll kMod = 1e9 + 7;

ll QPow(ll a, ll b) {
    ll ret = 1, bas = a;
    for(; b; b >>= 1, bas = bas * bas % kMod)
        if(b & 1) ret = ret * bas % kMod;
    return ret;
}

int n, mx, a[kN]; ll f[kN], g[kN]; ll m, m_inv;
int main() { 
    rd(n);
    for(int i = 1; i <= n; ++i) {
        rd(a[i]);
        m = (m + a[i]) % kMod;
        mx = std::max(mx, a[i]);
    }
    g[0] = (kMod - QPow(m, kMod - 2) * (m - 1) % kMod) % kMod;
    for(int i = 1; i <= mx; ++i) {
        g[i] = g[i - 1] + QPow(i - m + kMod, kMod - 2) * (m - 1) % kMod;
        f[i] = f[i - 1] + g[i - 1];
    }
    ll bg = 0;
    for(int i = 1; i <= n; ++i)
        bg = (bg + f[a[i]]) % kMod;
    ll ed = (m - 1) * (kMod - m) % kMod;
    printf("%lld\n", (bg - ed + kMod) % kMod);
    return 0;
}