/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
a, b, c からなる文字列 S が与えられます。
S の空でない部分列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、 2 つの部分列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。
部分列とは
S の部分列とは、S から 0 文字以上を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことをいいます。 例えば、ab, ac は abc の部分列ですが、ca, bb は abc の部分列ではありません。
制約
- S は
a,b,cからなる長さ 1 以上 3 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
abbc
出力例 1
11
同じ文字が隣合わない部分列は以下の 11 個です。
a( S の 1 文字目)b( S の 2 文字目)b( S の 3 文字目)c( S の 4 文字目)ab( S の 1,2 文字目)ab( S の 1,3 文字目)ac( S の 1,4 文字目)bc( S の 2,4 文字目)bc( S の 3,4 文字目)abc( S の 1,2,4 文字目)abc( S の 1,3,4 文字目)
2 番目と 3 番目のもののように、文字列として一致しても、取り出す位置が異なるならば区別することに注意してください。
入力例 2
cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca
出力例 2
378217423
998244353 で割った余りを出力してください。
Score : 400 points
Problem Statement
You are given a string S consisting of a, b, c.
Find the number of non-empty subsequences of S in which no two adjacent characters are the same, modulo 998244353.
Two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.
What is a subsequence?
A subsequence of S is a string obtained by removing zero or more characters from S and concatenating the remaining characters in their original order. For example,ab, ac are subsequences of abc, but ca, bb are not subsequences of abc.
Constraints
- S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of
a,b,c.
Input
The input is given from Standard Input in the following format:
S
Output
Output the answer.
Sample Input 1
abbc
Sample Output 1
11
The subsequences in which no two adjacent characters are the same are the following 11:
a(the 1st character of S)b(the 2nd character of S)b(the 3rd character of S)c(the 4th character of S)ab(the 1st, 2nd characters of S)ab(the 1st, 3rd characters of S)ac(the 1st, 4th characters of S)bc(the 2nd, 4th characters of S)bc(the 3rd, 4th characters of S)abc(the 1st, 2nd, 4th characters of S)abc(the 1st, 3rd, 4th characters of S)
Note that, as with the 2nd and 3rd entries, two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.
Sample Input 2
cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca
Sample Output 2
378217423
Output the count modulo 998244353.