← 返回题目列表

AtCoder · abc456_c

F. 不相邻

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个字符串 S 组成 a, b, c.

查找非空的个数 子字符串 of S 其中没有两个相邻字符相同,模 998244353.

如果两个子字符串取自不同的位置,则它们被视为不同,即使它们与字符串相同。

什么是子串? A 子字符串 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S。 例如, ab 是一个子串 abc,但是 ac 不是以下的子串 abc.

约束

  • S 是长度介于 1 和 3 \times 10^5,包含在内,由以下组成 a, b, c.

输入

输入由标准输入按以下格式给出:

S

输出

输出答案。


示例输入 1

abbc

示例输出 1

6

没有两个相邻字符相同的子串有以下六个:

  • a (来自 1st 到 1st 字符 S)
  • b (来自 2到 2第一个字符 S)
  • b (来自 3rd 到 3rd 字符 S)
  • c (来自 4至 4第一个字符 S)
  • ab (来自 1st 到 2第一个字符 S)
  • bc (来自 3rd 到 4第一个字符 S)

请注意,与 2nd 和 3rd 条目,如果两个子字符串取自不同的位置,则它们被视为不同,即使它们与字符串相同。


示例输入 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

示例输出 2

760