subsequence 1 - 题解

标签与难度

标签: 动态规划, 组合数学, 字符串, 计数DP, DP优化难度: 2100

题目大意喵~

主人你好呀，喵~ 这道题是这样的：

我们有两个只包含数字（'0' 到 '9'）的字符串 s 和 t，它们的长度分别是 n 和 m。题目保证它们的首位都不是 '0'。

任务是，要从字符串 s 中找出所有有效的子序列，这些子序列作为一个正整数看待时，要比字符串 t 代表的整数更大。我们需要计算出这样子序列的总数，并且答案要对 998244353 取模，因为结果可能会非常大哦！

这里有几个需要注意的小细节，喵~：

一个子序列是“有效”的，当且仅当它的首位字符不是 '0'。
两个子序列如果构成的字符在 s 中的位置不同，就被认为是不同的子序列。举个例子，如果 s 是 "1223"，那么从第2个字符'2'和第4个字符'3'组成的子序列 "23"，与从第3个字符'2'和第4个字符'3'组成的子序列 "23" 是不同的。

解题思路分析

喵~ 看到“子序列计数”这类问题，我们的第一反应通常就是动态规划（DP）啦！这是一个非常强大的工具，可以帮我们系统地解决这类问题。

为了不漏掉任何一种情况，也不重复计算，我们可以把所有比 t 大的有效子序列分成两大类来考虑：

长度大于 m 的子序列：如果一个有效子序列的长度比 t 的长度 m 要长，那么它代表的整数值显然也比 t 大。
长度等于 m 的子序列：如果一个子序列的长度恰好等于 m，那我们就需要逐位比较，看它是否在字典序上大于 t。

下面我们就来逐一分析怎么计算这两类的数量吧，呐！

第一类：长度大于 `m` 的子序列

对于任何一个长度 k > m 的有效子序列，它都满足条件。所以我们的目标是计算出所有长度为 m+1, m+2, ..., n 的有效子序列的数量。

一个子序列是否“有效”取决于它的第一个字符。所以，我们可以遍历 s 中的每一个字符 s[i]，考虑把它作为子序列的第一个字符。

如果 s[i] 是 '0'，那它就不能作为有效子序列的开头，我们直接跳过，喵~
如果 s[i] 不是 '0'，太棒啦！我们可以把它作为开头。接下来，我们需要从 s 中 s[i] 后面的 n - 1 - i 个字符里，再挑选 k-1 个字符来组成一个长度为 k 的子序列。

对于一个固定的开头 s[i]（s[i] != '0'）和固定的总长度 k（k > m），我们能构成的子序列数量就是从后面 n - 1 - i 个字符中选出 k-1 个，方案数就是组合数 $C(n - 1 - i, k - 1)$ 。

所以，第一类的总数就是把所有可能的 i 和 k 的情况加起来：

\text{Ans}_1 = \sum_{i=0}^{n-1} \left( [s[i] \neq '0'] \times \sum_{k=m+1}^{n} C(n-1-i, k-1) \right)

其中 [s[i] != '0'] 是一个指示函数，如果条件成立则为1，否则为0。

第二类：长度等于 `m` 的子序列

这部分稍微复杂一点，喵~ 我们需要找到 s 中长度为 m 且字典序大于 t 的子序列。这正是动态规划大显身手的地方！

我们定义一个二维DP数组 dp[i][j]，它的含义是： dp[i][j]: 只考虑 s 的前 i 个字符（s[0...i-1]），能够构成与 t 的前 j 个字符（t[0...j-1]）完全相同的子序列的方案数。

接下来我们来推导状态转移方程：在计算 dp[i][j] 时，我们正在考察 s 的第 i 个字符 s[i-1]。我们有两种选择：

不使用 s[i-1]：那么构成 t 的前 j 个字符的方案数，就完全来自于 s 的前 i-1 个字符，即 dp[i-1][j]。
使用 s[i-1]：这只有在 s[i-1] == t[j-1] 的时候才有可能。如果相等，s[i-1] 就可以作为 t 的前 j 个字符中的最后一个。那么，我们只需要用 s 的前 i-1 个字符构成 t 的前 j-1 个字符即可，方案数是 dp[i-1][j-1]。

所以，状态转移方程就是：

dp[i][j] = dp[i-1][j] + \begin{cases} dp[i-1][j-1] & \text{if } s[i-1] == t[j-1] \\ 0 & \text{if } s[i-1] \neq t[j-1] \end{cases}

Base Case: dp[i][0] = 1 for all i \ge 0，因为空的前缀（长度为0）可以由 s 的任意前缀通过“什么都不选”这种唯一的方案构成。

有了 dp 数组，我们怎么计算比 t 大的子序列数量呢？

我们可以遍历 s 中的每个字符 s[i-1] 和 t 中的每个字符 t[j-1]。假设我们正在构建一个长度为 m 的子序列，并且已经匹配到了第 j 位。

如果此时 s[i-1] > t[j-1]，一个绝佳的机会出现啦！这意味着，我们可以用 s 的前 i-1 个字符构成与 t 的前 j-1 个字符完全相同的子序列（方案数为 dp[i-1][j-1]），然后选择 s[i-1] 作为我们子序列的第 j 个字符。因为 s[i-1] > t[j-1]，此时我们的子序列已经确定比 t 大了！

那么，剩下的 m-j 个字符呢？我们可以在 s 中 s[i-1] 后面的 n-i 个字符里任意挑选 m-j 个字符来填满我们的子序列。挑选的方案数是 $C(n-i, m-j)$ 。

所以，每当遇到 s[i-1] > t[j-1]，我们就给总答案增加 dp[i-1][j-1] \times C(n-i, m-j)。别忘了，这个子序列的第一个字符也不能是 '0'。不过，因为 t 的首位不是 '0'，而我们是在 s[i-1] > t[j-1] 或者 s[i-1] == t[j-1] 的情况下进行匹配，所以只要 j>1 或者 s[i-1] 本身不为 '0'，就基本能保证有效性。我们的DP定义本身就是匹配 t，所以自然排除了前导零的情况。

总结与预处理

综上所述，我们的总答案就是 $\text{Ans}_1 + \text{Ans}_2$ 。在计算过程中，我们需要频繁使用组合数 $C(n,k)$ 。因为 n 的范围可达3000，我们可以预处理一个组合数表 C[i][j]，使用杨辉三角（Pascal's Triangle）的递推公式 $C(i, j) = C(i-1, j) + C(i-1, j-1)$ 在 $O(n^2)$ 时间内完成。

最终的算法流程：

预处理组合数 C[i][j] 模 998244353。
计算第一类答案（长度 > m）：双重循环遍历 i 和 k，累加 C(n-1-i, k-1)。
计算第二类答案（长度 == m）： a. 初始化并填充 dp 数组。 b. 遍历 i 和 j，当 s[i-1] > t[j-1] 时，累加 dp[i-1][j-1] * C(n-i, m-j) 到答案中。
将两部分答案相加取模，就是最终结果啦！

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 定义一个大大的常量作为模数，喵~
const int MOD = 998244353;
const int MAXN = 3005;

// 用于存放预处理的组合数
long long combinations[MAXN][MAXN];
// DP数组
long long dp[MAXN][MAXN];

// 预处理组合数 C(i, j)
void precompute_combinations(int n) {
    for (int i = 0; i <= n; ++i) {
        combinations[i][0] = 1; // C(i, 0) = 1
        for (int j = 1; j <= i; ++j) {
            combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;

    long long total_ans = 0;

    // --- 第一部分：计算长度大于 m 的有效子序列数量 ---
    // 遍历 s 中的每个字符，尝试将其作为子序列的第一个字符
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') {
            continue; // 首位不能是 '0'，跳过！
        }
        // 对于一个合法的开头 s[i]，我们需要从后面的 n-1-i 个字符中挑选 k-1 个
        // k 是子序列的总长度，范围从 m+1 到 n
        // 这里的内层循环可以优化，但为了清晰，我们先这么写
        // 实际上，我们是从 s[i] 后面的 n-1-i 个字符中，挑选 m 到 n-1-i 个字符
        for (int len_suffix = m; len_suffix <= n - 1 - i; ++len_suffix) {
            total_ans = (total_ans + combinations[n - 1 - i][len_suffix]) % MOD;
        }
    }

    // --- 第二部分：计算长度等于 m 且字典序大于 t 的子序列数量 ---
    // dp[i][j]: 用 s 的前 i 个字符，构成 t 的前 j 个字符的方案数
    // 初始化DP数组
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1; // 构成空前缀的方案数总是1
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = 0;
        }
    }

    // 填充DP数组并计算答案
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // Case 1: 不使用 s[i-1]
            dp[i][j] = dp[i - 1][j];
            
            // Case 2: 尝试使用 s[i-1]
            if (s[i - 1] == t[j - 1]) {
                // 如果 s[i-1] 和 t[j-1] 匹配，那么可以由 s 的前 i-1 个字符构成 t 的前 j-1 个字符
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
            } else if (s[i - 1] > t[j - 1]) {
                // 关键点！如果 s[i-1] > t[j-1]
                // 我们可以用 s 的前 i-1 个字符构成 t 的前 j-1 个字符（方案数 dp[i-1][j-1]）
                // 然后选择 s[i-1] 作为第 j 个字符，此时子序列已经比 t 大了
                // 剩下的 m-j 个字符可以从 s 的后 n-i 个字符中任意挑选
                if (n - i >= m - j) { // 确保有足够的字符可供选择
                    long long ways_to_form_prefix = dp[i - 1][j - 1];
                    long long ways_to_form_suffix = combinations[n - i][m - j];
                    total_ans = (total_ans + ways_to_form_prefix * ways_to_form_suffix) % MOD;
                }
            }
        }
    }

    cout << total_ans << endl;
}

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 预处理组合数，因为 n 最大是 3000
    precompute_combinations(3000);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N^2 + T \cdot (N^2 + N \cdot M))$
- 预处理组合数 combinations 的时间复杂度是 $O(N^2)$ ，其中 $N$ 是字符串 s 的最大可能长度。
- 对于每组测试数据：
  - 计算第一类答案（长度 > m）的循环是 $O(N \cdot N) = O(N^2)$ 。
  - 计算第二类答案（长度 == m）的DP过程是 $O(N \cdot M)$ 。
- 所以总的时间复杂度是 $O(N^2 + T \cdot (N^2 + N \cdot M))$ 。考虑到 $N, M \le 3000$ ，这是可以通过的。
空间复杂度: $O(N^2)$
- 我们使用了 combinations[MAXN][MAXN] 和 dp[MAXN][MAXN] 两个二维数组来存储组合数和DP状态。因此，空间复杂度是 $O(N^2 + N \cdot M)$ ，主要由组合数表决定，即 $O(N^2)$ 。

知识点总结

这道题真是一次有趣的冒险，喵！我们用到了不少好东西呢：

分类讨论思想: 将复杂问题分解成几个互不重叠的子问题（长度 > m 和长度 == m），是解决计数问题的常用策略。
动态规划 (DP): 特别是序列匹配类的DP，dp[i][j] 的定义和状态转移是解决这类问题的核心。
组合数学: $C(n,k)$ 的计算和应用是本题的关键。预处理组合数可以大大提高计算效率。
模块化算术: 在处理可能很大的数字时，记得随时取模，防止溢出。

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我，喵~ 加油！

subsequence 1 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一类：长度大于 m 的子序列 ​

第二类：长度等于 m 的子序列 ​

总结与预处理 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​