A6206 | Chain Contestant
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在另一个世界的 acgo 中，目前正在举办 AAC, ..., AJC 共 $10$ 种类型的比赛，接下来还将举办 $N$ 场比赛。
每场比赛的类型以字符串 $S$ 给出，$S$ 的第 $i$ 个字符为 $x$ 时，表示第 $i$ 场比赛为 A$x$C。
鹿 ac 君将从 $N$ 场比赛中选择至少一场参加，并且选择的比赛需要满足以下条件：
- 选中的比赛按原顺序抽取后，各种类型的比赛必须是连续的一段。
- 更严格地说，假设 ac 君参加了 $x$ 场比赛，且第 $i$ 场比赛的类型为 $T_i$，那么对于所有满足 $1 \le i < j < k \le x$ 的整数三元组 $(i, j, k)$，如果 $T_i = T_k$，则必须有 $T_i = T_j$。
请你求出 ac 君可以选择参赛的方案数对 $998244353$ 取模的结果。
注意，如果存在某场比赛 $c$，在一种选择中参加了而在另一种选择中没有，则这两种选择视为不同。
每场比赛的类型以字符串 $S$ 给出，$S$ 的第 $i$ 个字符为 $x$ 时，表示第 $i$ 场比赛为 A$x$C。
鹿 ac 君将从 $N$ 场比赛中选择至少一场参加，并且选择的比赛需要满足以下条件：
- 选中的比赛按原顺序抽取后，各种类型的比赛必须是连续的一段。
- 更严格地说，假设 ac 君参加了 $x$ 场比赛，且第 $i$ 场比赛的类型为 $T_i$，那么对于所有满足 $1 \le i < j < k \le x$ 的整数三元组 $(i, j, k)$，如果 $T_i = T_k$，则必须有 $T_i = T_j$。
请你求出 ac 君可以选择参赛的方案数对 $998244353$ 取模的结果。
注意，如果存在某场比赛 $c$，在一种选择中参加了而在另一种选择中没有，则这两种选择视为不同。
输入格式
输入以以下格式从标准输入读入。
> $N$ $S$
> $N$ $S$
输出格式
请输出一个整数作为答案。
输入输出样例
输入 #1
4 BGBH
输出 #1
13
输入 #2
100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF
输出 #2
330219020
## 限制
- $1 \le N \le 1000$
- $|S| = N$
- $S$ 只包含大写英文字母
## 样例解释 1
例如，选择第 $1,3$ 场比赛，或选择第 $2,4$ 场比赛，都是满足条件的方案。
而选择第 $1,2,3,4$ 场比赛时，ABC 类型的比赛没有连成一段，对于三元组 $(i, j, k) = (1, 2, 3)$ 不满足条件。
另外，全部不参加比赛也是不允许的。
满足题意的参赛方案共有 $13$ 种。
## 样例解释 2
注意，答案需要对 $998244353$ 取模。
- $1 \le N \le 1000$
- $|S| = N$
- $S$ 只包含大写英文字母
A 到 J## 样例解释 1
例如，选择第 $1,3$ 场比赛，或选择第 $2,4$ 场比赛，都是满足条件的方案。
而选择第 $1,2,3,4$ 场比赛时，ABC 类型的比赛没有连成一段，对于三元组 $(i, j, k) = (1, 2, 3)$ 不满足条件。
另外，全部不参加比赛也是不允许的。
满足题意的参赛方案共有 $13$ 种。
## 样例解释 2
注意，答案需要对 $998244353$ 取模。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？