题解 | #躲藏#

这并非简单的字符串匹配（如 KMP 算法处理的子串问题），也非最长公共子序列（LCS）问题。这是一个经典的固定模式子序列计数问题，可以通过动态规划 (Dynamic Programming) 或 有限状态自动机 (Finite State Machine) 的思想在线性时间内解决。

由于模式串 的长度极短且固定，我们可以定义 DP 的状态来追踪模式串匹配的进度。

状态定义： 我们维护四个变量，分别记录截至当前扫描到的字符位置，能够形成模式串前缀的子序列数量：

1. (cnt_c): 能够形成前缀 "c" (或 "C") 的子序列数量。
2. (cnt_cw): 能够形成前缀 "cw" (或 "Cw", "cW" 等) 的子序列数量。
3. (cnt_cwb): 能够形成前缀 "cwb" (忽略大小写) 的子序列数量。
4. (cnt_cwbc): 能够形成完整目标 "cwbc" (忽略大小写) 的子序列数量。

状态转移逻辑： 遍历输入字符串的每一个字符 ，根据其不区分大小写的值进行状态更新：

• 如果遇到字符 'c'：
  • 它可以作为模式串的结尾：将当前的 （已形成的 "cwb" 数量）累加到 中。这意味着每一个现存的 "cwb" 都可以和当前这个 'c' 组合成一个新的 "cwbc"。
  • 它可以作为模式串的开头：将 加 1。这意味着我们发现了一个新的起始点。
• 如果遇到字符 'w'：
  • 它可以承接前缀 "c" 形成 "cw"：将当前的 累加到 中。
• 如果遇到字符 'b'：
  • 它可以承接前缀 "cw" 形成 "cwb"：将当前的 累加到 中。
• 其他字符：忽略。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 2000120420010122;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    while (cin >> s) {
        ll cnt_c = 0;
        ll cnt_cw = 0;
        ll cnt_cwb = 0;
        ll ans = 0;

        for (const char c : s) {
            if (c == 'c' || c == 'C') {
                ans = (ans + cnt_cwb) % MOD;
                cnt_c = (cnt_c + 1) % MOD;
            } else if (c == 'w' || c == 'W') {
                cnt_cw = (cnt_cw + cnt_c) % MOD;
            } else if (c == 'b' || c == 'B') {
                cnt_cwb = (cnt_cwb + cnt_cw) % MOD;
            }
        }

        cout << ans << "\n";
    }

}