← 返回题单

题单练习状态压缩DP

← 上一题下一题 →

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$，在一种选择中参加了而在另一种选择中没有，则这两种选择视为不同。

输入格式

输入以以下格式从标准输入读入。 $N$ $S$

输出格式

请输出一个整数作为答案。

输入输出样例

输入 #1

4
BGBH

输出 #1

输入 #2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

输出 #2

330219020

C++ 编辑器

输入

输出