题解 | 小红的小球染色期望

题目信息

题目编号: ACM359
题目名称: 小红的小球染色期望
难度: 1800（较难）

一、DP方程定义

状态定义

dp[i] 表示有 i 个白色小球时，小红操作次数的期望值。

边界条件

dp[0] = dp[1] = 0：只有0个或1个球时，只能操作0次。

dp[2] = 1：只有2个球时，只能操作1次。

状态转移方程

对于 n 个球，小红第一次有 (n-1) 种选择（选择相邻的两个球）：

如果选择位置 i 和 i+1 的两个球（1 ≤ i ≤ n-1）
染色后，这两个球变红，将原序列分成两个独立的部分：左边：i-1 个白球；右边：n-i-1 个白球；中间的红球将两边隔开，互不影响

每种选择的概率为 1/(n-1)，所以：

$dp[n] = 1 + \frac{1}{n-1} \sum_{i=1}^{n-1} (dp[i-1] + dp[n-i-1])$

这里：

1 表示当前这次操作
后面的求和表示剩余两部分的期望操作次数

二、复杂度优化

优化前（暴力）：O(n²)

如果直接按上面的公式计算，每个 dp[i] 需要遍历所有可能的分割点，总复杂度为 O(n²)。

优化后：O(n)

观察求和式：

$\sum_{i=1}^{n-1} (dp[i-1] + dp[n-i-1]) = \sum_{i=0}^{n-2} dp[i] + \sum_{i=0}^{n-2} dp[i] = 2 \sum_{i=0}^{n-2} dp[i]$

关键优化：引入前缀和数组 sum[i] = dp[0] + dp[1] + ... + dp[i]

则转移方程简化为：

$dp[n] = 1 + \frac{2 \times sum[n-2]}{n-1}$

这样每个状态只需要 O(1) 时间计算，总复杂度降为 O(n)。

代码实现：

dp[i] = sum[i-2] * 2 % mod * inv(i-1) % mod + 1;
sum[i] = (sum[i-1] + dp[i]) % mod;  // 维护前缀和

三、概率论和逆元技巧

1. 期望的线性性质

期望满足线性性质：

$E[X + Y] = E[X] + E[Y]$

这道题中，总期望 = 当前操作(1次) + 左边期望 + 右边期望。

2. 模意义下的除法 = 乘以逆元

在模运算中，a / b (mod M) 需要转化为 a × b⁻¹ (mod M)。

3. 费马小定理求逆元

当模数 M = 10⁹ + 7 是质数时，根据费马小定理：

$b^{M-1} \equiv 1 \pmod{M}$

因此：

$b^{-1} \equiv b^{M-2} \pmod{M}$

代码实现快速幂：

int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int inv(int x) {
    return power(x, mod - 2);  // x的逆元 = x^(mod-2)
}

4. 取模运算的注意事项

由于涉及多次乘法，需要每步都取模防止溢出：

dp[i] = sum[i-2] * 2 % mod * inv(i-1) % mod + 1;

计算顺序：(sum[i-2] * 2) % mod，然后乘以 inv(i-1)，再模，最后加1。

完整AC代码

#include <iostream>
using namespace std;
#define int long long
int dp[2020200], sum[1010100];
const int mod = 1e9 + 7;

int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int inv(int x) {
    return power(x, mod - 2);
}

signed main() {
    int n, i;
    cin >> n;
    dp[2] = sum[2] = 1;
    for(i = 3; i <= n; i++) {
        dp[i] = sum[i-2] * 2 % mod * inv(i-1) % mod + 1;
        sum[i] = (sum[i-1] + dp[i]) % mod;
    }
    cout << dp[n] % mod;
}

总结

这道题的精髓在于：

DP建模：将期望问题转化为递推关系
前缀和优化：从 O(n²) 优化到 O(n)
逆元技巧：在模运算下正确处理除法运算

时间复杂度：O(n log mod)（主要是计算逆元的快速幂）

空间复杂度：O(n)

关键要点

期望DP的核心：分情况讨论，每种情况的期望 × 概率，然后求和
前缀和优化：发现求和式的对称性，避免重复计算
逆元计算：费马小定理在质数模下求逆元
模运算：每步都要取模，防止溢出