C - Not Adjacent Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

a, b, c からなる文字列 S が与えられます。

S の空でない部分文字列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。

ただし、 2 つの部分文字列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。

部分文字列とは S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

  • S は a, b, c からなる長さ 1 以上 3 \times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

abbc

出力例 1

6

同じ文字が隣合わない部分文字列は以下の 6 個です。

  • a ( S の 1 文字目から 1 文字目まで)
  • b ( S の 2 文字目から 2 文字目まで)
  • b ( S の 3 文字目から 3 文字目まで)
  • c ( S の 4 文字目から 4 文字目まで)
  • ab ( S の 1 文字目から 2 文字目まで)
  • bc ( S の 3 文字目から 4 文字目まで)

2 番目と 3 番目のもののように、文字列として一致しても、取り出す位置が異なるならば区別することに注意してください。

入力例 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

出力例 2

760

Score : 300 points

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty substrings of S in which no two adjacent characters are the same, modulo 998244353.

Two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

What is a substring? A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab is a substring of abc, but ac is not a substring 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

6

The substrings in which no two adjacent characters are the same are the following six:

  • a (from the 1st to the 1st character of S)
  • b (from the 2nd to the 2nd character of S)
  • b (from the 3rd to the 3rd character of S)
  • c (from the 4th to the 4th character of S)
  • ab (from the 1st to the 2nd character of S)
  • bc (from the 3rd to the 4th character of S)

Note that, as with the 2nd and 3rd entries, two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

760