#P18070. Reverse KMP
Reverse KMP
Reverse KMP
题目描述
对长度为 的字符串 ,定义前缀函数 为最大的整数 ,满足
$$0\le\ell<i,\qquad s_1s_2\cdots s_\ell=s_{i-\ell+1}s_{i-\ell+2}\cdots s_i.$$即前 个字符构成的字符串的最长相等真前缀与后缀的长度,没有非空匹配时为 。
给定数组 和包含 种不同字符的字母表,求有多少个长度为 的字符串,其前缀函数恰为 。答案对 取模。数组可能不对应任何字符串,此时答案为 。
输入格式
第一行整数 。每组数据第一行两个整数 ,第二行 个整数 。
,,,。所有测试用例的 之和不超过 。
输出格式
每组输出一个整数,表示字符串数量对 取模的结果。
样例 1
输入
3
3 3
0 1 2
7 3
0 0 0 1 2 3 0
7 3
0 0 0 1 2 3 1
输出
3
24
0