bzoj#P3879. SvT

SvT

题目描述

(我并不想告诉你题目名字是什么鬼)

有一个长度为 nn 的仅包含小写字母的字符串 SS,下标范围为 [1,n][1,n]

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在 SS 中出现的起始位置来表示),求这些后缀两两之间的 LCP\text{LCP}(最长公共前缀)的长度之和。一对后缀之间的 LCP\text{LCP} 长度仅统计一遍。

输入格式

第一行两个正整数 n,mn,m,分别表示 SS 的长度以及询问的次数。

接下来一行有一个字符串 SS

接下来有 mm 组询问,对于每一组询问,均按照以下格式在一行内给出:首先是一个整数 tt,表示共有多少个后缀。接下来 tt 个整数分别表示 tt 个后缀在字符串 SS 中的出现位置。

输出格式

对于每一组询问,输出一行一个整数,表示该组询问的答案。由于答案可能很大,仅需要输出这个答案对于 2333333333333333323333333333333333(一个巨大的质数)取模的余数。

7 3
popoqqq
1 4
2 3 5
4 1 2 5 6
0
0
2

样例说明

对于询问一,只有一个后缀 oqqq,因此答案为 00

对于询问二,有两个后缀 poqqq 以及 qqq,两个后缀之间的 LCP\text{LCP}00,因此答案为 00

对于询问三,有四个后缀 popoqqqopoqqqqqqqq,其中只有 qqqqq 两个后缀之间的 LCP\text{LCP} 不为 00,且长度为 22,因此答案为 22

数据规模与约定

对于 100%100\% 的测试数据,有 S5×105S\le 5\times 10^5,且 t3×106\sum t\le 3\times 10^6

提示

特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次。

题目来源

By YGY