题解 | #躲藏#_牛客博客

这道题需要格外注意一句话：

不区分大小写。

所以考虑设 $dp_{i,0/1/2/3}$ 表示以 $i$ 结尾，最后一位恰好匹配到 cwbc 的第 $0 / 1 / 2 / 3$ 个字符的方案数。

然后稍微压一下状态，写出状态转移方程：（代码中才是正确的，下面的稍微简化了一下书写，意会一下即可）

$\begin{aligned}dp_0&\leftarrow dp_0+(s[i]='c')\\ dp_1&\leftarrow dp_1+dp_0\times(s[i]='w')\\ dp_2&\leftarrow dp_2+dp_1\times(s[i]='b')\\ dp_3&\leftarrow dp_3+dp_2\times(s[i]='c')\end{aligned}$

#include<cstdio>
#include<cstring>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e6 + 5;
char s[N]; int dp[4];
signed main(){
    while (scanf("%s", s + 1) != EOF) {
        int len = strlen(s + 1);
        dp[0] = dp[1] = dp[2] = dp[3] = 0;
        for (int i = 1; i <= len; ++i) {
            dp[0] += s[i] == 'c' || s[i] == 'C';
            dp[1] += (s[i] == 'w' || s[i] == 'W') * dp[0];
            dp[2] += (s[i] == 'b' || s[i] == 'B') * dp[1];
            dp[3] += (s[i] == 'c' || s[i] == 'C') * dp[2];
        }
        print(dp[3] % 2000120420010122), putchar('\n');
    }
}