#P13792. [toyota2023spring final] Forbidden Pattern

    ID: 12993 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-计数 DP自动机 DP预处理下一出现位置预计算转移

[toyota2023spring final] Forbidden Pattern

题目描述

给定一个由 A 和 B 组成,长度为 NN 的字符串 SS。

你可以重复进行如下操作 00 次或多次:

  • 从 SS 中选择连续的 22 个字符,这两个字符不是 AB,将其删除。然后,将剩下的左右(可能为空的)字符串连接起来,作为新的 SS。

请你求出,经过若干次操作后,可能得到的不同字符串有多少种。答案对 998244353998244353 取模。

输入格式

输入通过标准输入给出,格式如下:

NN SS

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
BBA

输出 #1

3

输入输出样例 #2

输入 #2

5
ABABA

输出 #2

3

输入输出样例 #3

输入 #3

9
BABBAAAAB

输出 #3

14

输入输出样例 #4

输入 #4

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

输出 #4

3073910

说明/提示

限制条件

  • 2≤N≤1062 \leq N \leq 10^6
  • SS 是由 A 和 B 组成的长度为 NN 的字符串

样例解释 1

经过操作后,可能得到的字符串有 A、B、BBA 共 33 种。

样例解释 2

经过操作后,可能得到的字符串有 A、ABA、ABABA 共 33 种。

由 ChatGPT 4.1 翻译