Dwendwen的快乐暑假

暑假来了，身在华东师范大学的Dwendwen开心地准备回家过暑假了。在玩耍的过程中，突然有个学妹问她一个问题：
给定字符串序列Q<s1,…,sn>，产生一个序列P，其产生方法如下：
1. Q=<s1,…,sn> 
2. Q中每个字符串si将会被其所有前缀所代替，从而产生序列P
例如：
1. Q=<aab,ab>

2. 产生P=<a,aa,aab,a,ab>

共有26个正整数d₁,…,d₂₆分别表示着小写字母a,…,z的贡献。
每个字符串si的总贡献值计算方式是si串每个字母贡献值的乘积(mod m)。
现在想要知道对于Q序列中每个字符串s_i，在P序列中有多少个字符串是其前缀，并且满足字符串总贡献值大于字符串s_i。

第一行输入一个T(1 <= T <= 8)，表示T个测试样例。

对于每个测试样例，第一行给出n(1 <= n <= 5000)和m(1 <= m <= 1e9+7)。

第二行给出26个正整数d₁,…,d₂₆(1 <= di <= 1e5)分别表示着小写字母a,…,z的贡献。

接下来给出n行，每行一个字符串。保证字符串中每个字符都是小写，且字符串总长度不超过200000。

对于每个测试样例，输出共n个结果，分别代表每个字符串si在P中满足条件字符串的数量。注意每行末尾不要输出空格。

1
2 15
2 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aab
ab

3 0

Compiler
C C++ Java Python2 Python3

use advanced editor

Code