#P10348. 五五开

    ID: 9466 传统题 1000ms 512MiB 尝试: 83 已通过: 4 难度: 8 上传者: 标签>CF2400提高+/省选-模意义不变量补集计数线性 DP计数 DP滚动数组广度优先搜索状态编码快速幂

五五开

五五开(fiveopen)


题目描述

我们称两个由 a,b,c 构成的字符串 SS 和 TT 是五五开的,当且仅当可以对 SS 进行有限次如下操作变为 TT:

  • 选择一个 ii(1≤i<∣S∣1\le i< |S|)满足 SiS_i 与 Si+1S_{i+1} 不同
  • 将 SiS_i 和 Si+1S_{i+1} 同时改为第三种字符(即 a,b,c 中与 Si,Si+1S_i,S_{i+1} 均不同的那个字符)

给定 SS,求有多少个 TT,满足 SS 和 TT 五五开。注意这里 SS 和 TT 五五开不代表 TT 和 SS 五五开。答案对 998244353 取模。

输入格式

一行,一个字符串 SS

输出格式

一行,一个整数表示答案

样例输入 1
ac
样例输出 1
2
样例输入 2
bbbba
样例输出 2
65
样例 3

见下发文件

数据范围

对于所有的数据,保证 2≤∣S∣≤2⋅1052\le |S|\le 2\cdot 10^5

Subtask 11(2020 分):∣S∣≤10|S|\le 10

Subtask 22(1010 分):保证所有字符都相等

Subtask 33(2020 分):保证前 ∣S∣−1|S|-1 个字符都相等,依赖 Subtask2

Subtask 44(5050 分):无特殊限制,依赖前面所有 Subtask