题解：P12674 「LAOI-8」Count

题意简述

给定一个长度为

n

的序列

A

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

思路

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

dp[i]：前 $i$ 个元素的所有合法划分的贡献之和。
g[i]：前 $i$ 个元素的合法划分方案数。

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

40

种可能值）：

sumDp[x]：所有以颜色 $x$ 为左端点的位置 $j$ 的 dp[j-1] 之和。
sumG[x]：所有以颜色 $x$ 为左端点的位置 $j$ 的 g[j-1] 乘以从 $j$ 到当前位置的乘积之和（动态更新）。
sumG2[x]：所有以颜色 $x$ 为左端点的位置 $j$ 的 g[j-1] 之和。

状态转移

初始化dp[0] = 0（空序列贡献为 $0$ ），g[0] = 1（空序列有 $1$ 种划分）。
从 $i=1$ 到 $n$ 遍历序列，对于每种颜色 $c$ （ $1$ 到 $40$ ），将 sumG[c] 乘以当前元素 $A_i$ （扩展未闭合区间）。
计算当前状态：

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

$g_i = sumG2_x + g_{i-1}$
更新辅助数组（将当前位置 $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

CPP

#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

是序列长度。

题解：P12674 「LAOI-8」Count

文章操作

题意简述

思路

状态转移

不要忘了取模！

Code

相关推荐

评论

题解：P12674 「LAOI-8」Count