题解 | #躲藏#

长春某理工acm月赛的某题出处，很难评。 正题：我们考虑线性转移，dp[i]表示“Cwbc”中以1~i前字母组成的单词的数量。那么该单词1到i的数量只能由上一个单词1到i-1转移而来，故状态转移为(i=1) dp[i]++, (i>=2)dp[i] += dp[i-1]。由于不区分大小写，故第i为既可以是大写也可以是小写。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 5e5 + 10, mod = 2000120420010122;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    string s1 = "cwbc", s2 = "CWBC";    
    string s;
    while(cin >> s)
    {
          map<int, int>mp;
          for(int i = 0; i < s.size(); i ++)
          {
              for(int j = 0; j < s1.size(); j ++)
              {
                  if(s[i] == s1[j] || s[i] == s2[j])
                  {
                     if(!j) mp[j] = (mp[j] + 1) % mod;
                     else mp[j] += mp[j - 1], mp[j] %= mod;
                  }
               }
           }
           cout << mp[s1.size() - 1] << '\n';        
    }

}