Yet Another Problem On a Subsequence - 题解

比赛与标签

比赛: Educational Codeforces Round 46 (Rated for Div. 2) 标签: combinatorics, dp 难度: *1900

题目大意喵~

主人，你好呀~！这道题是关于一种叫做 "good sequence" 的特殊序列的计数问题，听起来就很有趣对不对，喵~？

首先，我们来定义两种序列：

1. "好数组" (Good Array)：一个整数序列 a_1, a_2, ..., a_k 如果满足 a_1 = k - 1 并且 a_1 > 0，那它就是一个"好数组"啦。简单来说，就是数组的第一个元素的值，恰好比数组的长度小1，并且这个值要大于0。比如说，[3, -1, 44, 0] 就是一个好数组，因为它的第一个元素是3，长度是4，满足 3 = 4 - 1。

2. "好序列" (Good Sequence)：一个序列如果可以被切分成一个或多个"好数组"，那么它就是一个"好序列"。每个"好数组"都必须是原序列的一个连续子段，并且原序列的每个元素都恰好属于其中一个"好数组"。比如 [2, -3, 0, 1, 4] 就是一个好序列，因为它可以被切分成 [2, -3, 0] (一个好数组，a_1=2, 长度=3) 和 [1, 4] (一个好数组，a_1=1, 长度=2)。

我们的任务是：给定一个长度为 n 的序列，找出它有多少个子序列是"好序列"，然后把结果对 998244353 取模输出。

注意啦，是子序列哦！这意味着我们可以从原序列中按顺序挑选一些元素组成新的序列，不要求它们在原序列中是连续的！

解题思路喵！

一看到“子序列计数”这类问题，聪明的猫娘我呀，第一反应就是动态规划（DP）啦！这可是解决这类问题的万能钥匙呢，喵~

让我们来设计一下 DP 的状态吧！一个常见的技巧是倒着来思考。

DP 状态定义

我们定义 dp[i] 表示：只考虑原序列的后缀 a[i], a[i+1], ..., a[n]，从这个后缀中能构成多少个不同的"好序列"子序列。

我们的最终目标就是求出 dp[1]，也就是从整个序列 a[1...n] 中能构成的好序列数量。

DP 状态转移

我们从后往前计算 dp 数组，即从 i = n 遍历到 i = 1。对于每个 dp[i]，我们需要考虑元素 a[i] 的两种命运：

1. 不选择 a[i] 如果我们不把 a[i] 加入到我们的子序列中，那么所有可能的好序列就只能从后缀 a[i+1...n] 中构成了。这种情况下的方案数，正好就是我们已经（或者将要）算出来的 dp[i+1] 的值！所以，dp[i] 首先就包含了 dp[i+1] 的所有情况。

dp[i] = dp[i+1]

2. 选择 a[i] 如果选择 a[i]，那么它必须是所构成的"好序列"的第一个元素。为什么呢？因为子序列是按原序列的顺序选取的，a[i] 是我们当前能选的最靠前的元素了。

当 a[i] 作为第一个元素时，它也必须是这个"好序列"中第一个"好数组"的第一个元素。设 v = a[i]。根据"好数组"的定义，这个"好数组"的长度必须是 v + 1。

• 可行性判断：
  • 首先，v 必须大于 0 (v > 0)。
  • 其次，我们需要从 a[i] 后面的元素（即 a[i+1...n]）中再挑选出 v 个元素来凑成这个"好数组"。a[i+1...n] 中共有 n - i 个元素，所以我们必须保证 n - i >= v。

如果以上条件不满足，a[i] 就不能作为开头，我们只能跳过它，dp[i] 就等于 dp[i+1]。

如果条件满足，那么以 a[i] 开头的"好序列"可以分为两种情况：

• 情况 A：整个子序列就是一个"好数组" 我们已经有了 a[i]，还需要从它后面的 n - i 个元素中挑选 v 个。挑选的方法数就是组合数 C(n - i, v)。

• 情况 B：整个子序列由多个"好数组"构成 这个子序列的形式是 G_1 S'，其中 G_1 是第一个"好数组"，S' 是后面跟着的另一个"好序列"。 G_1 由 a[i] 和从 a[i+1...n] 中选出的 v 个元素组成。 S' 则是由 G_1 最后一个元素之后的元素构成的子序列。

  这个听起来有点复杂，我们换个角度来统计！我们枚举 G_1 的最后一个元素是原序列中的 a[k]（其中 k > i）。

  • G_1 的第一个元素是 a[i]，最后一个元素是 a[k]。
  • 我们还需要从 a[i+1] 到 a[k-1] 这 k - 1 - i 个元素中，挑选出 v - 1 个元素来填满 G_1 的中间部分。挑选的方法数是 C(k - 1 - i, v - 1)。
  • G_1 构造完成后，剩下的"好序列" S' 就要从 a[k+1...n] 中挑选元素来构成。这个方案数，不就是我们定义的 dp[k+1] 吗！
  • 所以，我们只需要遍历所有可能的 k（从 i + v 到 n），把 C(k - 1 - i, v - 1) * dp[k+1] 的结果累加起来，就得到了情况 B 的总方案数。

总结一下转移方程：

dp[i] = dp[i+1] + (如果 a[i] > 0 且 n-i >= a[i]) { C(n-i, a[i]) + Σ [k=i+a[i] to n] (C(k-i-1, a[i]-1) * dp[k+1]) }

为了计算组合数 C(n, r)，我们需要预处理阶乘和阶乘的逆元，这在模运算中是常规操作啦~

代码实现喵~

#include <iostream>
#include <vector>
#include <numeric>

// 加速一下I/O，让程序跑得像猫一样快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 模数，可不能忘了哦
const int MOD = 998244353;

// 快速幂，用来求逆元，(base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 根据费马小定理求模逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// N的最大值
const int MAXN = 1005;
// 预处理阶乘和阶乘逆元的数组
long long fact[MAXN];
long long invFact[MAXN];

// 预处理阶乘和逆元到 n
void precompute_factorials(int n) {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
}

// 使用预处理的阶乘计算组合数 C(n, r) % MOD
long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) {
        return 0; // r不合法，组合数为0
    }
    // C(n,r) = n! / (r! * (n-r)!)
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

int main() {
    fast_io();
    
    int n;
    std::cin >> n;

    // 预处理组合数需要用到的阶乘
    precompute_factorials(n);

    // 为了方便DP状态的映射，我们使用1-based的下标
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    // dp[i]: 从后缀 a[i...n] 中能构成的"好序列"数量
    // dp数组大小为n+2，dp[n+1]和dp[n+2]默认为0，作为DP的边界条件
    std::vector<long long> dp(n + 2, 0);

    // 从后往前进行动态规划
    for (int i = n; i >= 1; --i) {
        // Case 1: 不选择 a[i]
        // 那么方案数就等于从 a[i+1...n] 中构成的方案数
        dp[i] = dp[i+1];

        int v = a[i];

        // Case 2: 选择 a[i] 作为子序列的第一个元素
        // 这要求 a[i] 必须是一个"好数组"的开头
        // 一个以 v 开头的"好数组"长度为 v+1
        // 我们需要从 a[i+1...n] 中再选 v 个元素
        // 这需要 v > 0 并且后面的元素个数 n-i 足够多 (>= v)
        if (v > 0 && (n - i) >= v) {
            // 以 a[i] 开头的"好序列"可以是一个"好数组" G_1，
            // 也可以是 G_1 后面跟着另一个"好序列" S'

            // 贡献1：子序列只包含一个"好数组" G_1
            // 我们需要从后面的 n-i 个元素中选 v 个
            long long ways_one_good_array = nCr_mod_p(n - i, v);

            // 贡献2：子序列是 G_1 S' 的形式，其中 S' 非空
            // 我们枚举 G_1 的最后一个元素是原序列中的 a[k]
            // 那么 S' 必须从 a[k+1...n] 中构成，方案数是 dp[k+1]
            // 而 G_1 的 v-1 个中间元素需要在 a[i+1...k-1] 中选
            long long ways_multiple_good_arrays = 0;
            for (int k = i + v; k <= n; ++k) {
                // 从 a[i+1...k-1] 这 k-i-1 个元素中选 v-1 个
                long long combinations = nCr_mod_p(k - i - 1, v - 1);
                if (combinations == 0) continue; // 优化一下，如果组合数为0就不用算了
                
                // 剩下的部分从 a[k+1...n] 中构成，方案数是 dp[k+1]
                long long rest_ways = dp[k + 1];
                ways_multiple_good_arrays = (ways_multiple_good_arrays + (combinations * rest_ways) % MOD) % MOD;
            }
            
            // 把所有以a[i]开头的方案数加起来
            long long total_ways_starting_with_ai = (ways_one_good_array + ways_multiple_good_arrays) % MOD;
            // 更新 dp[i]
            dp[i] = (dp[i] + total_ways_starting_with_ai) % MOD;
        }
    }

    // dp[1] 就是从整个序列 a[1...n] 中能构成的"好序列"总数
    std::cout << dp[1] << std::endl;

    return 0;
}

复杂度分析的说

• 时间复杂度: O(n^2) 的说。我们有一个主循环 i 从 n 到 1，这是 O(n)。在循环内部，如果条件满足，会有一个 k 的循环，最坏情况下也是 O(n) 的。组合数查询是 O(1) 的，因为我们已经预处理了。所以总的时间复杂度是 O(n^2)，对于 n <= 1000 来说是完全可以接受的！
• 空间复杂度: O(n) 的说。我们用了 dp 数组、a 数组、fact 和 invFact 数组，它们的大小都和 n 呈线性关系，所以空间复杂度是 O(n)。

知识点与总结喵~

这道题真是太棒了，融合了多种算法思想，让猫娘我超兴奋的！

1. 动态规划 (DP): 核心思想！特别是倒序DP，通过定义 dp[i] 为后缀 a[i...n] 的解，使得计算当前状态时，所依赖的子问题（如 dp[i+1], dp[k+1]）都已经被解决了。
2. 组合数学 (Combinatorics): 当问题涉及到"选择"多少个元素时，就要想到组合数 C(n, r) 啦。记得要预处理阶乘和逆元来加速计算哦！
3. 分类讨论: DP 转移的核心在于清晰的分类。我们将 a[i] 的情况分为"不选"和"选"。对于"选"的情况，又细分为"只构成一个好数组"和"构成多个好数组"，这样逻辑就非常清晰，不容易出错了。

希望这篇题解能帮助到你，主人！如果还有不懂的地方，随时可以再来问我哦~ 祝你刷题愉快，早日成为算法大师，喵~！