躲藏【牛客tracker 每日一题】

躲藏

时间限制：1秒 空间限制：32M

知识点：动态规划

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

X H R l y b XHRlybXHRlyb和她的小伙伴C w b c CwbcCwbc在玩捉迷藏游戏。
C w b c CwbcCwbc藏在多个不区分大小写的字符串中。
好奇的X H R l y b XHRlybXHRlyb想知道，在每个字符串中C w b c CwbcCwbc作为子序列分别出现了多少次。
由于C w b c CwbcCwbc可能出现的次数过多，你只需要输出每个答案对2000120420010122取模后的结果。
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述：

输入数据有多行，每行有一个字符串。

输出描述：

输出数据应有多行，每行表示一个答案取模后的结果。

示例1

输入：

Cwbc

输出：

1

说明：

C w b c CwbcCwbc作为子序列仅出现了1 11次。

示例2

输入：

acdcecfwgwhwibjbkblcmcnco

输出：

81

说明：

C w b c CwbcCwbc作为子序列出现了3 4 = 81 3^4=8134=81次。

备注：

每行字符串长度不超过2 × 10 5 2×10^52×105，字符串总长度不超过10 6 10^6106。

解题思路

本题采用一维动态规划统计子序列出现次数，核心是用四个变量分别记录匹配到“ C ” ( a ) 、“ C w ” ( b ) 、“ C w b ” ( c ) 、“ C w b c ” ( d ) “C”(a)、“Cw”(b)、“Cwb”(c)、“Cwbc”(d)“C”(a)、“Cw”(b)、“Cwb”(c)、“Cwbc”(d)的子序列数量；遍历字符串每个字符（不区分大小写），遇′ C ′ / ′ c ′ 'C'/'c'′C′/′c′时，d dd累加c cc（当前C CC可作为最后一位完成C w b c CwbcCwbc匹配）且a aa自增（新增以当前C CC开头的子序列），遇′ W ′ / ′ w ′ 'W'/'w'′W′/′w′时b bb累加a aa（当前W WW匹配C CC后的w ww），遇′ B ′ / ′ b ′ 'B'/'b'′B′/′b′时c cc累加b bb（当前B BB匹配C w CwCw后的b bb），所有操作对给定模数取模；遍历结束后d dd即为“ C w b c ” “Cwbc”“Cwbc”作为子序列的次数。该方法时间复杂度为O ( l e n ( s ) ) O(len(s))O(len(s))，无额外空间开销，完美适配单字符串长度≤ 2 × 10 5 ≤2×10^5≤2×105、总长度≤ 10 6 ≤10^6≤106的规模，精准统计目标子序列的出现次数。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=2000120420010122;constll N=1e6+10;intmain(){string s;while(cin>>s){ll a=0,b=0,c=0,d=0;for(auto&i:s){if(i=='C'||i=='c')d=(d+c)%p,a++;if(i=='W'||i=='w')b=(b+a)%p;if(i=='B'||i=='b')c=(c+b)%p;}cout<<d<<endl;}return0;}