AC自动机+矩阵乘法 again...
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>#define ll unsigned long longusing namespace std;struct AcAutoMachine {
#define N 26 // 字典的节点数，比最大数据略大即可
#define M 26 // 字典的字母数，此为精确值int next[N][M], fail[N], data[N], size;int queu[N], head, tail;int code(const char &c) { // 将字符哈希成结点标号return c - 'a';}void clear(int x) {memset(next[x], -1, sizeof(next[x]));fail[x] = -1; data[x] = 0;}void init() {clear(0);size = 1;}void insert(char *str) {int p = 0, idx;while (*str) {idx = code(*str);if (next[p][idx] == -1) {clear(size);next[p][idx] = size++;}p = next[p][idx];str++;}data[p]++;}void buildac() {int p, pp, fp, fpp;head = tail = 0;queu[tail++] = 0;while (head < tail) {p = queu[head++];for (int i = 0; i < M; i++) {if ((pp = next[p][i]) != -1) {for (fp = fail[p]; fp != -1; fp = fail[fp]) {if ((fpp = next[fp][i]) != -1) {fail[pp] = fpp;// 将fail链上后继结点的权值加到前驱结点中，// 这样计算权值时就不需要遍历fail链，看情况是否需要。data[pp] += data[fpp];break;}}if (fp == -1) fail[pp] = 0;queu[tail++] = pp;} else { // 重构next，看题目是否需要if (p == 0) next[p][i] = 0;else next[p][i] = next[fail[p]][i];}}}}
} A;vector<int> sh;
char str[11];
int c;
ll mat1[26][26], mat2[26][26], mat3[26][26];void dfs(int s) {if (A.data[s]) return;sh.push_back(s);A.data[s]++;for (int i = 0; i < 26; i++)dfs(A.next[s][i]);
}int find(int x) {int l = 0, r = c - 1, m;while (l <= r) {m = (l + r) / 2;if (sh[m] < x) l = m + 1;else if (sh[m] > x) r = m - 1;else return m;}return -1;
}void buildmtx() {int i, j, k;memset(mat1, 0, sizeof(mat1));memset(mat2, 0, sizeof(mat2));for (i = 0; i < c; i++) {for (j = 0; j < 26; j++) {k = find(A.next[sh[i]][j]);if (k != -1) mat2[k][i]++;else mat2[c][i]++;}}mat2[c][c] = 26;c++;mat2[c][c-1] = mat2[c][c] = 1;for (i = 0; i <= c; i++)mat1[i][i] = 1;
}void mul(ll mat1[26][26], ll mat2[26][26]) {int i, j, k;for (i = 0; i <= c; i++) {for (j = 0; j <= c; j++) {mat3[i][j] = 0;for (k = 0; k <= c; k++)mat3[i][j] += mat1[i][k] * mat2[k][j];}}memcpy(mat1, mat3, sizeof(mat3));
}void test(ll mat[26][26]) {int i, j;printf("-------------\n");for (i = 0; i <= c; i++) {for (j = 0; j <= c; j++)printf("%2I64d ", mat[i][j]);printf("\n");}printf("-------------\n");
}int main() {int m, n, i;while (scanf("%d %d", &m, &n) != EOF) {A.init();for (i = 0; i < m; i++) {scanf("%s", str);A.insert(str);}A.buildac();sh.clear();dfs(0);sort(sh.begin(), sh.end());c = sh.size();buildmtx();while (n) {if (n & 1) mul(mat1, mat2);mul(mat2, mat2);n >>= 1;}printf("%I64u\n", mat1[c][0] + mat1[c-1][0]);}return 0;
}