分数: 400 点
问题陈述
给你一个字符串 S 组成 a, b, c.
查找非空的个数 子序列 of S 其中没有两个相邻字符相同,模数 998244353.
如果两个子序列取自不同的位置,则被认为是不同的,即使它们与字符串相同。
什么是子序列?
A 子序列 of S 是删除零个或多个字符后得到的字符串 S 并按原始顺序连接其余字符。 例如,ab, ac 是子序列 abc,但是 ca, bb 不是以下的子序列 abc.
约束
- S 是长度介于 1 和 3 \times 10^5,包含在内,由以下组成
a,b,c.
输入
输入由标准输入按以下格式给出:
S
输出
输出答案。
示例输入 1
abbc
示例输出 1
11
没有两个相邻字符相同的子序列如下 11:
a( 1st 字符 S)b( 2第一个字符 S)b( 3rd 字符 S)c( 4第一个字符 S)ab( 1圣, 2nd 个字符 S)ab( 1圣, 3rd 字符 S)ac( 1圣, 4个字符 S)bc( 2nd, 4个字符 S)bc( 3路, 4个字符 S)abc( 1圣, 2nd, 4个字符 S)abc( 1圣, 3路, 4个字符 S)
请注意,与 2nd 和 3rd 条目,如果两个子序列取自不同的位置,则被认为是不同的,即使它们与字符串相同。
示例输入 2
cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca
示例输出 2
378217423
输出计数模数 998244353.