#P17758. String
String
题目描述
给定一个长度为 的小写字母串 。你需要计算满足条件的长度为 的小写字母串 的数量,对 取模。
共有 个限制条件。第 个限制条件形如 ,其中 是若干个 中的区间组成的可重集。
一个串 满足第 个限制条件,当且仅当存在一个区间 ,使得:
这里 表示 的第 个字符到第 个字符组成的连续子串, 的含义类似。
输入格式
第一行包含一个整数 ,表示该测试点所属的子任务编号。
第二行包含三个整数 。
第三行包含一个长度为 的小写字母串 。
接下来描述 个限制条件。
对于每个 ,首先输入一行三个整数 ,表示该限制条件作用于 ,并且 。
接下来 行,每行两个整数 ,表示一个候选区间 。
输出格式
输出一行一个整数,表示满足所有限制条件的字符串 的数量对 取模后的结果。
样例 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\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.$$设
则有:
对于每个限制条件,满足:
对于每个候选区间,满足:
本题采用子任务捆绑测试。只有通过一个子任务中的所有测试点,才能获得该子任务的分数。
对于子任务中的"没有包含关系",其含义是:不存在两个不同的限制条件 ,满足
对于子任务中的"无交叉关系",其含义是:任意两个区间 与 要么不相交,要么一个包含另一个。
对于子任务中的"随机二元串",其含义是:在该子任务的每个测试点中,字符串 由数据生成器随机生成,且对于每个位置 , 独立等概率地从字符 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 | 无附加限制 |