#P17758. String

String

题目描述

给定一个长度为 nn 的小写字母串 ss。你需要计算满足条件的长度为 mm 的小写字母串 tt 的数量,对 998244353998244353 取模。

共有 kk 个限制条件。第 ii 个限制条件形如 (li,ri,Si)(l_i,r_i,S_i),其中 SiS_i 是若干个 ss 中的区间组成的可重集。

一个串 tt 满足第 ii 个限制条件,当且仅当存在一个区间 [l′,r′]∈Si[l',r']\in S_i,使得:

t[li,ri]=s[l′,r′].t[l_i,r_i]=s[l',r'].

这里 t[li,ri]t[l_i,r_i] 表示 tt 的第 lil_i 个字符到第 rir_i 个字符组成的连续子串,s[l′,r′]s[l',r'] 的含义类似。

输入格式

第一行包含一个整数 subtask_id\mathrm{subtask\_id},表示该测试点所属的子任务编号。

第二行包含三个整数 n,m,kn,m,k。

第三行包含一个长度为 nn 的小写字母串 ss。

接下来描述 kk 个限制条件。

对于每个 1≤i≤k1\le i\le k,首先输入一行三个整数 li,ri,cil_i,r_i,c_i,表示该限制条件作用于 t[li,ri]t[l_i,r_i],并且 ∣Si∣=ci|S_i|=c_i。

接下来 cic_i 行,每行两个整数 a,ba,b,表示一个候选区间 [a,b]∈Si[a,b]\in S_i。

输出格式

输出一行一个整数,表示满足所有限制条件的字符串 tt 的数量对 998244353998244353 取模后的结果。

样例 1

1
1 4 0
a
456976

样例 2

1
3 3 1
abc
1 2 0
0

样例 3

1
5 5 2
abcab
1 3 2
1 3
2 4
3 5 2
3 5
1 3
2

样例 4

1
6 4 3
abacba
1 4 3
1 4
2 5
3 6
2 3 2
2 3
3 4
3 4 2
3 4
4 5
2

样例 5

1
6 3 3
abcabc
1 3 3
1 3
2 4
4 6
1 3 2
1 3
3 5
1 3 2
1 3
4 6
1

样例 6

2
10 10 5
abacabadab
1 3 3
1 3
5 7
2 4
3 5 3
3 5
1 3
2 4
6 8 3
1 3
2 4
8 10
8 10 3
3 5
5 7
8 10
5 5 2
1 1
2 2
4

数据范围与子任务

对于所有测试数据,满足:

1≤subtask_id≤10.1\le \mathrm{subtask\_id}\le 10. $$1\le n\le 5\times 10^4,\quad 1\le m\le 2\times 10^5,\quad 0\le k\le 2\times 10^5.$$

设

sz=∑i=1kci,sz=\sum_{i=1}^k c_i,

则有:

0≤sz≤2×105.0\le sz\le 2\times 10^5.

对于每个限制条件,满足:

1≤li≤ri≤m,0≤ci.1\le l_i\le r_i\le m,\quad 0\le c_i.

对于每个候选区间,满足:

1≤a≤b≤n.1\le a\le b\le n.

本题采用子任务捆绑测试。只有通过一个子任务中的所有测试点,才能获得该子任务的分数。

对于子任务中的"没有包含关系",其含义是:不存在两个不同的限制条件 i,ji,j,满足

li≤lj≤rj≤ri.l_i\le l_j\le r_j\le r_i.

对于子任务中的"无交叉关系",其含义是:任意两个区间 [li,ri][l_i,r_i] 与 [lj,rj][l_j,r_j] 要么不相交,要么一个包含另一个。

对于子任务中的"随机二元串",其含义是:在该子任务的每个测试点中,字符串 ss 由数据生成器随机生成,且对于每个位置 1≤i≤n1\le i\le n,sis_i 独立等概率地从字符 a 与 b 中选择。

子任务 分值 附加限制
1 5 $n,m\le 8,\ k\le 8,\ sz\le 20$
2 7 $n,m\le 200,\ k\le 200,\ sz\le 500$
3 10 所有区间 $[l_i,r_i]$ 两两不相交
4 11 对每个 $i$,有 $c_i=1$
5 12 不存在两个限制区间 $[l_i,r_i]$ 之间有包含关系
6 12 任意两个区间 $[l_i,r_i]$ 要么不相交,要么一个包含另一个
7 9 $n\le 2000,\ m,k,sz\le 5000$
8 10 $n\le 3000,\ m,k,sz\le 2\times 10^5$
9 8 随机二元串
10 16 无附加限制