题解：「USACO 2024 Jan Platinum P2」Merging Cells（基于提供代码）

核心思路总览

本题是 区间DP + 概率递推 问题，核心通过“区间状态定义 + 合并概率计算 + 前缀和优化”求解。以区间 [l, r] 为核心状态，计算合并该区间所有细胞后，最终编号为 l 的概率（通过对称性和编号继承规则简化计算），整体复杂度 (O(N^2))，适配 (N=5000) 的规模。

关键背景与简化逻辑

1. 合并规则的核心观察

• 合并后的细胞编号由“大小+编号”决定：大小更大的优先，大小相等时取编号更大的。
• 区间 [l, r] 合并后的最终编号，必然是区间内“能主导所有合并”的细胞编号。
• 代码的核心简化：f[l][r] 仅存储“合并区间 [l, r] 后，最终编号为 l 的概率”，其他编号的概率通过类似逻辑推导（利用区间DP的对称性和转移传递）。

2. 合并概率的核心逻辑

• 合并 k 个细胞需 k-1 次合并，每次合并从 (当前细胞数 - 1) 对相邻细胞中均匀选择，概率为 (1/(当前可选对数))。
• 组合数学基础：k 个细胞的合并顺序总数为卡特兰数相关，但代码通过逆元直接计算“选择某相邻对合并”的概率权重（nyn[i] = 1/i mod MOD）。

核心状态与数组定义

完整代码（带关键注释）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010, mod = 1e9 + 7;

// 模加法：确保结果在[0, mod)范围内
inline void Add(int &x, int y) {
    x = (x + y >= mod ? x + y - mod : x + y);
}

// 模减法：确保结果在[0, mod)范围内
inline void Sub(int &x, int y) {
    x = (x - y < 0 ? x - y + mod : x - y);
}

// 快速幂：计算a^b mod mod（用于求逆元）
int qmi(int a, int b) {
    int r = 1;
    for (; b; b >>= 1) {
        if (b & 1) r = (ll)r * a % mod;
        a = (ll)a * a % mod;
    }
    return r;
}

int n, s[N], nyn[N];  // s：前缀和；nyn：逆元数组
int f[N][N], tmp[N];  // f：区间DP状态；tmp：临时累积数组

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    // 读取初始大小，计算前缀和s
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];  // s[i] = sum_{k=1 to i} s_k
    }

    // 预处理1~n的模逆元（nyn[i] = 1/i mod mod）
    for (int i = 1; i <= n; i++) {
        nyn[i] = qmi(i, mod - 2);
    }

    // 区间DP：按左端点l从大到小遍历（l从n到1）
    for (int i = 1; i <= n; i++) {  // 此处i实际为左端点l，代码中用i表示l
        memset(tmp, 0, sizeof tmp);  // 重置临时数组
        int sum = (i == 1);  // 初始sum：l=1时为1（单个细胞的概率基础），否则为0
        int pos = n;  // 分界点pos初始化：区间[r, r]的右边界
        Sub(tmp[n - 1], sum);  // 初始化tmp数组的负累积

        // 右端点j从n向l+1遍历（区间长度从大到小）
        for (int j = n; j > i; j--) {
            // 状态传递：将f[l][j]传递到f[l+1][j]（左端点右移的继承）
            if (f[i][j]) Add(f[i + 1][j], f[i][j]);

            // 累积概率sum：sum += tmp[j]，更新f[l][j]
            Add(sum, tmp[j]);
            Add(f[i][j], sum);
            // 乘以逆元：合并区间[l,j]时，可选相邻对数为(j-i)，概率权重1/(j-i)
            f[i][j] = (ll)f[i][j] * nyn[j - i] % mod;

            // 找到分界点pos：左子区间[l, pos-1]的和 ≤ 右子区间[pos, j]的和
            pos = min(pos, j);
            while (s[pos - 1] - s[i - 1] > s[j] - s[pos - 1]) {
                pos--;
            }

            // 更新sum和tmp数组：累积当前f[l][j]的贡献
            Add(sum, f[i][j]);
            Sub(tmp[pos - 1], f[i][j]);
            // 状态传递：更新f[l+1][j]和f[pos+1][j]（区间扩展的继承）
            Add(f[i + 1][j], f[i][j]);
            Sub(f[pos + 1][j], f[i][j]);
        }

        // 处理单个细胞的情况（l=r=i）：sum += tmp[i]，更新f[i][i]
        Add(sum, tmp[i]);
        Add(f[i][i], sum);
    }

    // 输出每个编号i的最终概率（f[i][i]）
    for (int i = 1; i <= n; i++) {
        cout << f[i][i] << '\n';
    }

    return 0;
}

核心DP流程拆解

1. 预处理阶段

• 前缀和数组 s：快速计算任意区间 [l, r] 的总大小（s[r] - s[l-1]），用于判断合并后的编号继承。
• 逆元数组 nyn：预处理 1~n 的模逆元，将“选择相邻对合并”的概率（1/(j-i)）转化为乘法（*nyn[j-i]）。

2. 区间DP遍历顺序

• 左端点 l 从 n 到 1 逆序遍历（代码中用 i 表示 l）。
• 右端点 j 从 n 到 l+1 逆序遍历，确保处理区间 [l, r] 时，所有子区间（如 [l+1, r]、[l, pos] 等）已计算完成。

3. 状态转移核心逻辑

（1）概率累积与权重计算

• sum 变量累积子区间传递的概率，结合 tmp 数组存储的临时贡献，更新当前区间 [l, j] 的基础概率。
• 乘以逆元 nyn[j-i]：合并区间 [l, j] 时有 j-i 对相邻细胞可选，均匀选择的概率为 1/(j-i)。

（2）分界点 pos 计算

• 找到区间 [l, j] 中，左子区间 [l, pos-1] 总大小 ≤ 右子区间 [pos, j] 总大小的最小 pos。
• 该 pos 决定了合并后的编号继承规则：左子区间主导则编号为 l，右子区间主导则编号为右子区间的主导编号。

（3）状态传递与优化

• 通过 Add(f[i+1][j], f[i][j]) 和 Sub(f[pos+1][j], f[i][j]) 传递概率，避免重复计算。
• tmp 数组用于存储负累积贡献，结合 sum 实现前缀和快速查询，将转移复杂度从 (O(N^3)) 优化到 (O(N^2))。

4. 最终结果

• f[i][i] 表示合并所有细胞后，最终编号为 i 的概率，直接输出即可。

关键难点解析

1. 状态简化设计

代码仅用 f[l][r] 存储“编号为 l 的概率”，而非存储所有可能编号的概率，通过区间扩展和传递，间接推导所有编号的最终概率，大幅降低空间复杂度。

2. 前缀和优化

tmp 数组和 sum 变量的配合，避免了对每个子区间的遍历求和，将转移效率从 (O(N^3)) 提升到 (O(N^2))，使其能处理 (N=5000) 的规模。

3. 模运算处理

通过 Add 和 Sub 函数确保模运算后结果非负，逆元的预处理确保除法转化为乘法的正确性，符合题目中模 (10^9+7) 的要求。

复杂度分析

• 时间复杂度：(O(N^2))，外层遍历左端点 l（(O(N))），内层遍历右端点 j（(O(N))），每个区间的转移操作均为 (O(1))（分界点 pos 的移动总次数为 (O(N^2))）。
• 空间复杂度：(O(N^2))，主要用于存储区间DP状态 f[N][N]，适配 (N=5000)（(5000 \times 5000 = 2500) 万，可用内存承载）。