【fjwc2015】Galaxy

2015年2月3日1,8280

【题目描述】

小X进入了平行宇宙,想在某个平行宇宙开始一段生活。平行宇宙之间用长度为N的仅含有A、B、C、D四个字母的序列标识。每一个由A,B,C,D组成的长度为N的序列标识着不同的平行宇宙。

有趣的是,不同的宇宙对应着小X的不同人生,在某些宇宙中,小X的人生过得并不愉快。

小X得到了M个特征碎片,特征碎片都为长度小于10的由A,B,C,D构成的序列。如果某个平行宇宙的标识序列包含某个特征碎片(即特征碎片为宇宙序列的子串),那么小X在这个平行宇宙过得不愉快。

小X能自由的进入任何一个平行宇宙,并且小X不想进入会让他过得不愉快的平行宇宙,请问小X有多少种选择?

 

【输入】

第一行为M(0 <= m <= 10), N (1 <= n <=2000000000), M为标识序列的个数,N为宇宙标识序列的长度

之后M行,每行一个特征标识序列。

每行的长度不超过10。

【输出】

一个整数,表示码农的选择数 mod 100000

 

【样例输入】

4 3

AB

AC

AD

AA

【样例输出】

36

 

【样例解释】

如序列ABC 包含AB,为不愉快的序列

序列BBB不包含任何特征序列,为愉快的序列。

题解

用AC自动机得出转移矩阵后矩乘

T T

模板错->滚粗