Dwendwen的快乐暑假
Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
13.33%(2/15)
Description:
暑假来了，身在华东师范大学的Dwendwen开心地准备回家过暑假了。在玩耍的过程中，突然有个学妹问她一个问题：
2. 产生P=<a,aa,aab,a,ab>
给定字符串序列Q<s1,…,sn>
1. Q=<s1,…,sn>
2. Q中每个字符串si将会被其所有前缀所代替，从而产生序列P
例如：
1. Q=<aab,ab>
每个字符串si的总贡献值计算方式是si串每个字母贡献值的乘积(mod m)。
现在想要知道对于Q序列中每个字符串si，在P序列中有多少个字符串是其前缀，并且满足字符串总贡献值大于字符串si。
Input:
第一行输入一个T(1 <= T <= 8)，表示T个测试样例。
对于每个测试样例，第一行给出n(1 <= n <= 5000)和m(1 <= m <= 1e9+7)。
第二行给出26个正整数d1,…,d26(1 <= di <= 1e5)分别表示着小写字母a,…,z的贡献。
接下来给出n行，每行一个字符串。保证字符串中每个字符都是小写，且字符串总长度不超过200000。
Output:
对于每个测试样例，输出共n个结果，分别代表每个字符串si在P中满足条件字符串的数量。注意每行末尾不要输出空格。
Sample Input:
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
Sample Output:
3 0
Submit