UOJ Logo Universal Online Judge

UOJ

#636. 【美团杯2021测试赛】中国式家长

附件下载 统计

通过这一道题目希望大家能够知道:我们归根结底还是一个正经算法竞赛。

本题来源于《中国式家长》中的一个小游戏。

游戏开始时会生成一个长度为 $n$ 的宝石序列,每个宝石按照从左到右的顺序被标号成 $1$ 到 $n$。每个宝石有类型和能量两种属性,宝石的类型有四种,分别用字母ABCD表示,在初始时每个宝石的能量都是 $1$。同时保证初始时不存在连续的三个相同类型的宝石。

蒜斜可以进行若干轮操作,每轮操作的流程如下:

  1. 选择结束游戏,当只剩下一个宝石的时候,蒜斜必须结束游戏。
  2. 选择并删除某一个当前还存在的宝石,删除后右侧的宝石会自动向左补齐。
  3. 令 $i$ 为当前最小的下标满足从左到右第 $i,i+1,i+2$ 个宝石的类型和能量都相同。如果这样的 $i$ 不存在,则这一轮结束,开始下一轮。否则这三个宝石会被移出游戏,同时在原来第 $i$ 个宝石的位置会出现一个类型和原来相同,能量比原来大 $1$ 的宝石。接着右侧的宝石会向左补齐,游戏回到这一步的开始,并继续从左到右寻找连续三个相同的宝石。

我们用 $A(x)$ 表示类型为 $A$ 能量为 $x$ 的宝石,下面是两个例子:

  1. 如果宝石序列是 A(1)A(1)B(1)A(1)A(1),那么在删除 B(1) 之后,结果序列为A(2)A(1)。
  2. 如果宝石序列是 A(3)A(3)A(2)A(2)A(1)A(1)B(1)A(1),那么在删除 B(1) 之后,结果序列为 A(4)。

蒜斜是一个全收集爱好者。她发现每一次开始这个小游戏,初始的宝石的数量、顺序和颜色都是完全相同的。而游戏中有一个传说级成就:合成出所有可能的结束状态。

在开始刷成就之前,蒜斜想让你帮她计算一下,一共有多少种不同的结束状态。

两个结束状态是不同的当且仅当剩下宝石的数量不同,或者存在一个下标 $i$ 满足两个状态中从左到右第 $i$ 个小球的类型或者能量不同。

输入格式

第一行一个整数 $n (1 \leq n \leq 10^6)$ 表示宝石序列的长度。

第二行一个长度为 $n$ 的由 ABCD 组成的字符串,表示初始的宝石序列。保证该序列中,不存在连续的三个相同的字符。

输出格式

输出一行一个整数,表示可能的结束状态个数。答案可能很大,对 $998244353$ 取模后输出。

样例输入一

input

5
AABAA

output

13

explanation

没有删除 B(1) 的情况(共 9 种):A(1)A(1)B(1)A(1)A(1), A(1)A(1)B(1)A(1), A(1)A(1)B(1), A(1)B(1)A(1)A(1), A(1)B(1)A(1), A(1)B(1), B(1)A(1)A(1), B(1)A(1), B(1)

删除了 B(1) 的情况(共 4 种):A(2)A(1), A(2), A(1)A(1), A(1)

因此一共有 13 种可能的结束状态。

样例输入二

input

16
ABCDABCDABCDABCD

output

42775

样例输入三

input

16
DAABBAACCBBAACCD

output

6314

限制与约定

Small Task: 初始序列相邻球颜色不同。

Large Task: 无特殊限制。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载