官方题解｜统计 acgo 的出现次数

题目解析

我们考虑使用动态规划来统计所有的以 a，c，g，o 结尾的子序列的数量。

令 $A, C, G, O$ 分别表示 a，c，g，o 结尾的子序列的数量。

遍历字符串 $S$，对于字符串 $S$ 中的每个字符 $S_i$，若其为 a，则将 $A$ 加一；若其为 b，则将 $B$ 更新为 $B + A$； 若其为 c，则将 $C$ 更新为 $C + B$； 若其为 d，则将 $D$ 更新为 $D + C$； 若为其他字符，则不做任何处理。

最终 $D$ 即为所求的答案。

AC代码

#include <bits/stdc++.h>

const std::string S = "#acgo";
constexpr int MOD = 998244353;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    std::string s; std::cin >> s;
    std::vector<int> dp(S.size());
    dp[0] = 1;
    for (auto &c : s) {
        auto p = S.find(c);
        if (p == std::string::npos) continue;
        dp[p] = (dp[p] + dp[p - 1]) % MOD;
    }
    std::cout << dp.back() << '\n';
    return 0;
}