← 返回比赛

已结束【提高组】GESP“飞翔杯”第三届季度赛

← 上一题下一题 →

A5031 | $蒙尘之镜$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

睡眼惺忪地，夏绯在回味刚刚的梦境。 梦境与一个字符串 $S = s_1 s_2 \dots s_m$ 有关。由于这个梦非常漫长，所以绯绯对其进行了一些压缩，将其表示为 $S = b_1^{a_1} b_2^{a_2} \dots b_n^{a_n}$。 绯绯称 $S$ 的子串（形如 $s_l s_{l + 1} \dots s_r$）为梦境的碎片；称一个碎片是镜像的，当且仅当其为回文串。 绯绯认为一个碎片的迷惘度为其镜像子串数；梦境的迷惘度为其所有碎片的迷惘度之和。形式化地说，梦境的迷惘度被定义为其所有子串的回文子串数之和。 现在，绯绯希望你可以求出梦境的迷惘度。由于绯绯认为得到完全精确的结果并无意义，所以你只需给出梦境迷惘度对 $998\,244\,353$ 取模后的值即可。

输入格式

第一行包含一个整数 $n$，表示压缩后信息的数目。 接下来 $n$ 行，第 $i$ 行包含一个整数 $a_i$ 和一个字符 $b_i$，表示压缩后的第 $i$ 条信息。

输出格式

共一行一个整数，表示梦境的迷惘度，对 $998\,244\,353$ 取模后的值。

输入输出样例

输入 #1

1
3 c

输出 #1

输入 #2

2
2 c
3 b

输出 #2

输入 #3

3
2 c
2 a
3 c

输出 #3

对于样例 1，注意到任意子串皆镜像，故长为 $x$ 的碎片的迷惘度即 $\frac{x(x + 1)}{2} = \binom{x + 1}{2}$。故答案为 $\sum_{l = 1}^3 \sum_{r = l}^3 \binom{r - l + 2}{2} = 15$。 对于所有数据，保证 $1 \le n \le 10^6$，$1 \le a_i \le 10^9$，$b_i \in \{\texttt{a}, \dots, \texttt{z}\}$。 测试点编号$n \le$$a_i \le$$b_i=$1, 2$10^2$$1$—3, 4$10^2$$10^2$—5, 6$10^2$——7, 8$10^3$$1$—9, 10$10^3$$10^3$—11, 12$10^3$——13, 14$10^5$$1$—15, 16$10^5$$10^3$—17~19$10^5$$10^5$—20, 21$10^5$—$\texttt{a}$22~24$10^5$——25———

C++ 编辑器

输入

输出