题目链接：https://www.nowcoder.com/acm/contest/87/B


       第一眼看以为是kmp，然后仔细一看是子序列，再看数据范围，暴力的话肯定会超时，所以这道题需要用动态规划来写，令 f[i][j],(j = 1,2,3,4) 表示前 i 个字符中，匹配了字符串”cwbc” 的前多少位，那么有转移方程：

                f[i][1] = (f[i−1][1] + (s[i] ==′ c′)) % Mod 

                f[i][2] = (f[i−1][2] + (s[i] ==′ w′)∗f[i−1][1]) % Mod 

                f[i][3] = (f[i−1][3] + (s[i] ==′ b′)∗f[i−1][2]) % Mod 

                f[i][4] = (f[i−1][4] + (s[i] ==′ c′)∗f[i−1][3]) % Mod

       但是数组的开小大概需要 35MB 左右，会超过内存限制，所以还需要优化一下。
       容易发现，每一个字符的状态都只从它前一个字符的状态转移过来，显然我们可以考虑使用滚动数组来优化空间开销。我们考虑去掉第一维的状态，只保留第二维的状态。那么转移方程就变为：

                f[1] = (f[1] + (s[i] ==′ c′)) % Mod 

                f[2] = (f[2] + (s[i] ==′ w′)∗f[1]) % Mod 

                f[3] = (f[3] + (s[i] ==′ b′)∗f[2]) % Mod

                f[4] = (f[4] + (s[i] ==′ c′)∗f[3]) % Mod
       同一个位置有且仅有一个字符，不难发现转移方程间是不会相互影响的。因此，省去第一维的状态

是正确的。


AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define ll long long
#define mod 2000120420010122
using namespace std;
string str;
ll dp[5];

int main()
{
  while(cin>>str){
    int len = str.length();
    memset(dp,0,sizeof(dp));
    for(int i=0;i<len;i++){
      str[i] = tolower(str[i]);
      dp[1] = (dp[1] + (str[i] == 'c')) % mod;
      dp[2] = (dp[2] + (str[i] == 'w') * dp[1]) % mod;
      dp[3] = (dp[3] + (str[i] == 'b') * dp[2]) % mod;
      dp[4] = (dp[4] + (str[i] == 'c') * dp[3]) % mod;
    }
    cout<<dp[4]<<endl;
  }
  return 0;
}