SCPC

简要题面

字符串中有多少子序列是scpc

题面

中南民族大学第七届程序设计竞赛火热进行中！当你正专注解题时，意外在小鸡留下的神秘宝箱前驻足。小鸡自信地认为无人能破解密码，竟将解锁线索大大方方刻在了宝箱表面！

锈迹斑驳的箱体上篆刻着一串神秘的小写字母字符串，而你敏锐地发现：这个字符串中所有能组合成 $scpc$ 的子序列数量，正是开启这个宝箱的关键密码！

那么，聪明的你可以打开小鸡的宝箱吗？

注：子序列是指通过从原始序列中删除某些元素（可能一个、多个或不删除）但不改变剩余元素的相对位置所形成的新序列，例如 $sacpc$ 通过删除元素 $a$ 可以得到子序列 $scpc$ 。

输入描述

一行一个字符串 $s(1 \le \lvert s \rvert \le 10^7)$

输出描述

一行一个数字表示答案

由于答案可能过大，请对 $998244353$ 取模

输入输出样例

输入 #1

scppcsscpspccsp

输出 #1

28

说明/提示

解法

用动态规划来维护子序列的计数。我们用 dp[i] 表示形成前 i 个字符的部分子序列数量，其中：

• dp[1] 统计 s 的数量
• dp[2] 统计 sc 的数量
• dp[3] 统计 scp 的数量
• dp[4] 统计 scpc 的数量（最终答案）

遍历字符串时，我们根据不同的字符进行如下转移：

• 遇到 's'：
  • dp[1] += 1，即统计 s 的出现次数
• 遇到 'c'：
  • dp[4] += dp[3]，即 scpc 的个数增加 scp 的个数
  • dp[2] += dp[1]，即 sc 的个数增加 s 的个数
• 遇到 'p'：
  • dp[3] += dp[2]，即 scp 的个数增加 sc 的个数

参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll dp[5];
int main(){
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<s.length();i++){
        if(s[i]=='s'){
            dp[1]=(dp[1]+1)%mod;
        }
        else if(s[i]=='c'){
            dp[4]=(dp[4]+dp[3])%mod;
            dp[2]=(dp[1]+dp[2])%mod;
        }
        else if(s[i]=='p'){
            dp[3]=(dp[2]+dp[3])%mod;
        }
    }
    cout<<dp[4]<<'\n';
    return 0;
}