102154: [AtCoder]ABC215 E - Chain Contestant
Description
Score : $500$ points
Problem Statement
AtCoder in another world holds $10$ types of contests called AAC, ..., AJC. There will be $N$ contests from now on.
The types of these $N$ contests are given to you as a string $S$: if the $i$-th character of $S$ is $x$, the $i$-th contest will be A$x$C.
AtCoDeer will choose and participate in one or more contests from the $N$ so that the following condition is satisfied.
- In the sequence of contests he will participate in, the contests of the same type are consecutive.
- Formally, when AtCoDeer participates in $x$ contests and the $i$-th of them is of type $T_i$, for every triple of integers $(i,j,k)$ such that $1 \le i < j < k \le x$, $T_i=T_j$ must hold if $T_i=T_k$.
Find the number of ways for AtCoDeer to choose contests to participate in, modulo $998244353$.
Two ways to choose contests are considered different when there is a contest $c$ such that AtCoDeer participates in $c$ in one way but not in the other.
Constraints
- $1 \le N \le 1000$
- $|S|=N$
- $S$ consists of uppercase English letters from
AthroughJ.
Input
Input is given from Standard Input in the following format:
$N$ $S$
Output
Print the answer as an integer.
Sample Input 1
4 BGBH
Sample Output 1
13
For example, participating in the $1$-st and $3$-rd contests is valid, and so is participating in the $2$-nd and $4$-th contests.
On the other hand, participating in the $1$-st, $2$-nd, $3$-rd, and $4$-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple $(i,j,k)=(1,2,3)$.
Additionally, it is not allowed to participate in zero contests.
In total, there are $13$ valid ways to participate in some contests.
Sample Input 2
100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF
Sample Output 2
330219020
Be sure to find the count modulo $998244353$.
Input
题意翻译
给定一个长度为 $N(1 \le N \le 10^3)$ 的只含有字符 $\texttt{A}$ 到 $\texttt{J}$ 字符串 $S$，你需要寻找出一个字符串子集 $T$ 满足： - 任意一对 $(i,j,k)(1 \le i < j < k \le N)$ 的三元组，如果 $T_i=T_k$，那么 $T_i=T_j$ 一定成立。 求出子集 $T$ 的方案数，答案对 $998244353$ 取模。 Translated by @[cjh20090318](/user/577880)。Output
分数：500分
问题描述
在另一个世界中的AtCoder举办10种类型的竞赛，分别称为AAC，...，AJC。从现在开始将举办N场竞赛。
- 这些N场比赛的类型将以字符串S的形式给出给你：如果S的第i个字符为x，则第i场比赛将是A$x$C。
- AtCoDeer将从这N场比赛中选择并参加一场或多场比赛，以满足以下条件：
- 他将参加的比赛序列中，同类型的比赛是连续的。
求解AtCoDeer选择参加比赛的方法数，对998244353取模。
如果在一种选择中AtCoDeer参加比赛c，而在另一种选择中不参加比赛c，则认为两种选择是不同的。
约束条件
- 1≤N≤1000
- |S|=N
- S由从
A到J的大写字母组成。
输入
从标准输入按以下格式获取输入：
$N$ $S$
输出
打印答案作为整数。
样例输入1
4 BGBH
样例输出1
13
例如，参加第1场和第3场是有效的，参加第2场和第4场也是有效的。
另一方面，参加第1场，第2场，第3场和第4场是无效的，因为参加ABC的参赛者不是连续的，违反了对于三元组$(i,j,k)=(1,2,3)$的条件。
此外，不允许参加零场比赛。
总共有13种有效的方式参加一些比赛。
样例输入2
100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF
样例输出2
330219020
请确保找到对998244353取模后的计数。