← 返回题目列表

AtCoder · abc456_d

D. 不相邻 2

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

分数: 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.