题解：P12674 「LAOI-8」Count

· · 题解

题意简述

给定一个长度为 n 的序列 A，要求将其划分为若干个区间，每个区间的左右端点的值必须相等。每个划分的贡献为所有非空区间内元素的乘积之和，求所有合法划分的贡献之和。（结果要取模）

思路

考虑动态规划。定义两个状态数组：

如果只是简单的 DP 肯定会爆炸（再看一眼多看一眼就会……），所以为优化计算，维护三个辅助数组（针对序列中的 40 种可能值）：

状态转移

  1. 初始化dp[0] = 0（空序列贡献为 0），g[0] = 1（空序列有 1 种划分）。

  2. 从 i=1 到 n 遍历序列，对于每种颜色 c（1 到 40），将 sumG[c] 乘以当前元素 A_i（扩展未闭合区间）。

  3. 计算当前状态：

    dp_i = (sumDp_x + dp_{i-1}) + (sumG_x + g_{i-1} \times A_i) g_i = sumG2_x + g_{i-1}

  4. 更新辅助数组（将当前位置 i 作为左端点加入）：

    sumDp_x \gets sumDp_x + dp_{i-1} sumG2_x \gets sumG2_x + g_{i-1} sumG_x \gets sumG_x + g_{i-1} \times A_i

不要忘了取模！

Code

#include <iostream>
using namespace std;

const int mod = 998244353;
const int N = 250000;
const int C = 40;

int n;
int A[N];
long long dp[N + 1];  // dp[i] 表示前 i 个元素的合法划分的贡献之和
long long g[N + 1];   // g[i] 表示前 i 个元素的合法划分方案数

// 辅助数组，针对每种颜色（1到40）
long long sumDp[C + 1];  // sumDp[x]：所有以 x 为左端点的 j 的 dp[j-1] 之和
long long sumG2[C + 1];  // sumG2[x]：所有以 x 为左端点的 j 的 g[j-1] 之和
long long sumG[C + 1];   // sumG[x]：所有以 x 为左端点的 j 的 g[j-1] 乘以从 j 到当前位置的乘积之和

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    // 初始化
    dp[0] = 0;
    g[0] = 1;
    for (int c = 1; c <= C; c++) {
        sumDp[c] = 0;
        sumG2[c] = 0;
        sumG[c] = 0;
    }
    for (int i = 1; i <= n; i++) {
        int x = A[i - 1];  // 当前元素的值（1到40）
        // 步骤1：更新 sumG，将所有未闭合区间的乘积乘以当前元素
        for (int c = 1; c <= C; c++) {
            sumG[c] = (sumG[c] * x) % mod;
        }
        // 步骤2：计算 dp[i] 和 g[i]
        // dp_i：sumDp[x]（以 x 为左端点的所有 j 的 dp[j-1] 之和）加上 dp[i-1]
        long long dp_i = (sumDp[x] + dp[i - 1]) % mod;
        // s2：sumG[x]（以 x 为左端点的所有 j 的 g[j-1] * 乘积）加上 g[i-1] * A[i]
        long long s2 = (sumG[x] + g[i - 1] * x) % mod;
        dp[i] = (dp_i + s2) % mod;
        // g[i]：sumG2[x]（以 x 为左端点的所有 j 的 g[j-1] 之和）加上 g[i-1]
        g[i] = (sumG2[x] + g[i - 1]) % mod;
        // 步骤3：更新辅助数组，将当前位置 i 作为新的左端点加入
        sumDp[x] = (sumDp[x] + dp[i - 1]) % mod;
        sumG2[x] = (sumG2[x] + g[i - 1]) % mod;
        sumG[x] = (sumG[x] + g[i - 1] * x) % mod;
    }
    cout << dp[n] << endl;
    return 0;
}

对每个元素，需要更新 40 种颜色的辅助数组，时间复杂度 O(40 \times n)，其中 n 是序列长度。