徐老师的咒语吟唱
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在游戏中学会了一个超级大招——灭世雷霆！
释放这个技能需要进行一段咒语吟唱，这段咒语是一个长度为 $n$ 的字符串 $S$
徐老师的吟唱过程分为 $m$ 个部分，第 $i$ 个部分有 $k_i$ 种不同的吟唱方式可以选择，每种吟唱方式都是一个由小写字母组成的字符串
徐老师现在找到一种可以便捷释放技能的方法：
也就是在灭世雷霆的咒语上找到 $m$ 个互不相交的子串:$[x_1,y_1],[x_2,y_2] \dots [x_m,y_m]$，满足任意一个子串 $[x_i,y_i]$ 是第 $i$ 部分的吟唱方式之一，并且 $x_i < y_i < x_{i+1}$
这里我们认为两种吟唱方案只要存在任意的 $i$ 使得 $x1_i != x2_i$ 或者 $y1_i != y2_i$，则这两种吟唱方案是不同的
现在徐老师想知道，自己有多少种不同的吟唱方案可以释放出灭世雷霆？
这个方案数可能会很大，所以方案数只要对 $998244353$ 取模即可
输入格式
第一行包含两个整数 $n,m$，含义如题
第二行包含 $n$ 个用空格隔开的字符，表示字符串 $S$
接下来 $m$ 行，每行第一个整数 $k_i$ 表示第 $i$ 个吟唱部分有 $k_i$ 种吟唱方式
接下来 $k_i$ 个用空格隔开的字符串表示每一种吟唱方式
以下用 $len$ 表示吟唱方式的长度
对于 $100\%$ 的数据： $n \leq 10^5, m \leq 50, \sum{k_i} \leq 100, k_i \leq 5, len \leq 10$
其中：
对于 $15\%$ 的数据： $k_i = 1$
另有 $35\%$ 的数据： $m == 1$
另有 $10\%$ 的数据： $len == 1$
另有 $10\%$ 的数据： $len \leq 2$
特别的保证：保证吟唱的每个部分不存在相同的吟唱方式
对于 $100\%$ 的数据： $n \leq 10^5, m \leq 50, \sum{k_i} \leq 100, k_i \leq 5, len \leq 10$
其中：
对于 $15\%$ 的数据： $k_i = 1$
另有 $35\%$ 的数据： $m == 1$
另有 $10\%$ 的数据： $len == 1$
另有 $10\%$ 的数据： $len \leq 2$
特别的保证：保证吟唱的每个部分不存在相同的吟唱方式
输出格式
输出一个整数目标吟唱方案的数量，由于答案可能会很大，请将答案对 $998244353$ 取模样例
11 3
x l s a k c s p n o i
1 xls
1 ak
2 csp noi2提示
有两种方案能够释放技能：`[xls-ak-csp]` 和 `[xls-ak-noi]`2023暑CSP-S复赛集训模拟赛一
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-28 22:00
- 结束于
- 2023-8-7 22:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 21
