Moe's CF Life

Appearance

F. Number of Subsequences - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 674 (Div. 3) 标签: combinatorics, dp, strings, *2000 难度: *2000

题目大意喵~ ​

主人你好呀~！这道题是这样的呐：

我们拿到一个长度为 n 的字符串 s，它里面只包含小写字母 'a', 'b', 'c' 和问号 '?'。

字符串里每一个 '?' 都可以变成 'a', 'b', 'c' 中的任意一个。如果总共有 k 个问号，那我们总共就能变出 3^k 种不同的、只含 'a', 'b', 'c' 的字符串。

我们的任务就是，把这 3^k 个字符串里所有的 "abc" 子序列个数全部加起来，然后把这个巨大的总数对 10^9 + 7 取模。

比如说，如果 s 是 a?c，那么：

  • '?' 变成 'a'，得到 aac，有 1 个 "abc" 子序列。
  • '?' 变成 'b'，得到 abc，有 1 个 "abc" 子序列。
  • '?' 变成 'c'，得到 acc，有 1 个 "abc" 子序列。 所以总数就是 1 + 1 + 1 = 3 个啦！很简单对不对喵？

解题思路，和喵娘一起攻克它！ ​

看到 n 最大有 200000，而且还有 3^k 种可能性，直接暴力生成所有字符串再一个个去数，肯定会超时到天上去的喵！(ﾉ>ω<)ﾉ 所以，我们需要一个更聪明的办法，这就要请出我们算法竞赛的老朋友——动态规划 (DP) 啦！

我们的目标是计算所有可能字符串中 "abc" 子序列的总数。我们可以从左到右遍历字符串 s，在每一步都维护一些关键信息。这个关键信息就是：当我们处理到第 i 个字符时，由前 i 个字符构成的所有可能的前缀字符串中，各种子序列的总数是多少。

具体来说，我们需要维护以下几个计数器：

  1. count_a: 所有可能的前缀字符串中，子序列 "a" 的总数。
  2. count_ab: 所有可能的前缀字符串中，子序列 "ab" 的总数。
  3. count_abc: 所有可能的前缀字符串中，子序列 "abc" 的总数。这个就是我们最终的答案！

但是，只维护这三个还不够哦。想一想，当遇到一个新的 'a' 时，它能和谁组成新的 "a" 子序列呢？是和它前面的空子序列呀！所以我们还需要一个计数器：

  1. count_empty: 所有可能的前缀字符串中，空子序列的总数。这其实就等于所有可能的前缀字符串的总数，因为每个字符串都有一个空子序列嘛。

现在，我们来推导状态转移的逻辑，喵~

假设我们已经处理完了前 i-1 个字符，得到了 count_empty, count_a, count_ab, count_abc 的值。现在我们来看第 i 个字符 s[i]：

  • 如果 s[i] 是 'a':

    • 新的 "a" 子序列，是由这个 'a' 和之前所有字符串的空子序列组成的。之前有多少种可能的字符串，就有多少个空子序列，也就是 count_empty。
    • 所以，count_a 的值需要增加 count_empty。
    • count_ab 和 count_abc 不会因为一个 'a' 而直接增加，所以它们的值保持不变。

  • 如果 s[i] 是 'b':

    • 新的 "ab" 子序列，是由这个 'b' 和之前所有 "a" 子序列组成的。
    • 所以，count_ab 的值需要增加 count_a。
    • 其他计数器不变。

  • 如果 s[i] 是 'c':

    • 新的 "abc" 子序列，是由这个 'c' 和之前所有 "ab" 子序列组成的。
    • 所以，count_abc 的值需要增加 count_ab。
    • 其他计数器不变。

  • 如果 s[i] 是 '?' (最有趣的部分来啦！):

    • 这个 '?' 可以是 'a', 'b', 'c' 三种情况的任意一种。我们需要把这三种情况的贡献全部加起来。
    • 对于之前已经形成的每一种子序列（比如 "a", "ab", "abc"），无论当前 '?' 变成什么，它们都会被保留下来。因为之前的字符串都变成了 3 份（一份结尾是'a', 一份是'b', 一份是'c'），所以之前的所有子序列计数都要乘以 3。
    • 接下来考虑新形成的子序列：
      • 如果 '?' 变成 'a'，会新增加 count_empty 个 "a" 子序列。
      • 如果 '?' 变成 'b'，会新增加 count_a 个 "ab" 子序列。
      • 如果 '?' 变成 'c'，会新增加 count_ab 个 "abc" 子序列。
    • 把这些贡献整合起来，我们就能得到新的计数值了！
      • new_count_abc = 3 * count_abc + count_ab
      • new_count_ab = 3 * count_ab + count_a
      • new_count_a = 3 * count_a + count_empty
      • new_count_empty = 3 * count_empty (字符串总数也乘以3)

在实现 '?' 的逻辑时，要注意更新顺序哦！如果我们先更新 count_a，那么在计算 new_count_ab 时就会用到本轮更新后的 count_a，这就错啦！我们需要的是上一轮的 count_a。所以，要么用临时变量存一下，要么像AC代码那样，从 count_abc 开始反向更新，这样就能保证每次计算都用的是上一轮的值啦！

就这样一步步从左到右递推，遍历完整个字符串后，count_abc 里存的就是我们想要的最终答案了，喵~

代码实现，看喵娘的魔法！ ​

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

int main() {
    // 使用快速I/O，让程序跑得飞快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    long long MOD = 1000000007;

    // 我们用动态规划的思想来解决这个问题。
    // 在遍历字符串的过程中，我们维护四个计数器：
    
    // count_empty: 从已处理前缀能形成的所有字符串中，空子序列的总数。
    //              这其实就等于已处理前缀能形成的不同字符串的总数。初始为1，代表一个空字符串。
    long long count_empty = 1;
    
    // count_a: ... 子序列 'a' 的总数。
    long long count_a = 0;
    
    // count_ab: ... 子序列 'ab' 的总数。
    long long count_ab = 0;
    
    // count_abc: ... 子序列 'abc' 的总数。这是我们的最终目标！
    long long count_abc = 0;

    for (char c : s) {
        if (c == 'a') {
            // 新的 'a' 子序列由这个 'a' 和之前所有的空子序列构成。
            // 空子序列的数量就是之前能形成的字符串总数，也就是 count_empty。
            count_a = (count_a + count_empty) % MOD;
        } else if (c == 'b') {
            // 新的 'ab' 子序列由这个 'b' 和之前所有的 'a' 子序列构成。
            count_ab = (count_ab + count_a) % MOD;
        } else if (c == 'c') {
            // 新的 'abc' 子序列由这个 'c' 和之前所有的 'ab' 子序列构成。
            count_abc = (count_abc + count_ab) % MOD;
        } else { // c == '?'
            // 如果是问号，它可以是 'a', 'b', 'c' 中的任意一个。
            // 1. 对于已有的子序列，它们的数量会翻3倍，因为每种已有字符串都衍生出3个新字符串。
            // 2. 此外，还会形成新的子序列：
            //    - 如果 '?' 变成 'c'，会增加 count_ab 个 'abc' 子序列。
            //    - 如果 '?' 变成 'b'，会增加 count_a 个 'ab' 子序列。
            //    - 如果 '?' 变成 'a'，会增加 count_empty 个 'a' 子序列。
            //    - 字符串总数（即空子序列数）也翻3倍。
            // 为了使用上一轮的计数值进行计算，我们从后往前更新。
            
            // 新的 'abc' 总数 = 原来的 * 3 + 新增的 (当 '?'='c')
            long long next_abc = (3LL * count_abc + count_ab) % MOD;
            // 新的 'ab' 总数 = 原来的 * 3 + 新增的 (当 '?'='b')
            long long next_ab = (3LL * count_ab + count_a) % MOD;
            // 新的 'a' 总数 = 原来的 * 3 + 新增的 (当 '?'='a')
            long long next_a = (3LL * count_a + count_empty) % MOD;
            // 新的字符串总数 = 原来的 * 3
            long long next_empty = (3LL * count_empty) % MOD;

            // 用新值覆盖旧值
            count_abc = next_abc;
            count_ab = next_ab;
            count_a = next_a;
            count_empty = next_empty;
        }
    }

    std::cout << count_abc << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n) 的说。我们只把长度为 n 的字符串从头到尾扫了一遍，每次循环里的操作都是常数时间的，所以效率非常高哦！
  • 空间复杂度: O(1) 的说。我们只用了几个固定的变量来存储DP状态，不管字符串 n 有多长，占用的内存都是一样的，超级节省空间呢！

知识点与总结 ​

主人，这道题是不是很有趣呀？喵娘来帮你总结一下这次学到的东西吧！

  1. DP与组合计数的结合: 这道题的核心就是把动态规划的思想用在了组合计数上。我们不是去数某一个具体字符串的子序列，而是在每一步都计算所有可能情况下子序列的总和。
  2. DP状态的巧妙设计: (count_empty, count_a, count_ab, count_abc) 这个状态设计得非常精妙，它包含了递推所需要的全部信息，让复杂的计数问题变得线性可解。
  3. 处理通配符'?'的思路: 当遇到不确定的字符时，一个常见的处理方式就是分类讨论并汇总贡献。对于'?'，我们把它看成是'a', 'b', 'c'三种情况的叠加，既要考虑原有子序列数量的倍增，也要考虑新产生的子序列。
  4. 空间优化（滚动数组）: 我们发现 dp[i] 只和 dp[i-1] 有关，所以完全没必要开一个大数组，用几个变量滚动更新就足够了。这是DP优化中非常实用的技巧！

希望这篇题解能帮到主人哦！多练习类似的DP题目，你也会变得和喵娘一样厉害的喵~！(＾• ω •＾)♡

Released under the MIT License.

Copyright © 2024-present Moe