#include<cstring> #include<cstdio> #include<queue> usingnamespace std; typedefunsignedlonglong ull; constint CHARACTER_SET_SIZE = 26; constint MAX_N = 7; constint MAX_L = 6; int n, l; int trie[MAX_N * MAX_L][CHARACTER_SET_SIZE], tot; bool permitted[MAX_N * MAX_L]; int fail[MAX_N * MAX_L]; char str[MAX_L]; structMatrix { ull m[MAX_N * MAX_L][MAX_N * MAX_L]; Matrix() { memset(m, 0, sizeof(m)); } }; inlinevoidinit(); voidinsert(char s[]); voidbuildACAutomaton(); Matrix operator*(const Matrix& x, const Matrix& y); Matrix operator+(const Matrix& x, const Matrix& y); Matrix quickPow(Matrix a, int b); ull quickPow(ull a, int b); ull isometricSeriesSum(ull a, int n); Matrix isometricSeriesSum(Matrix a, int n); Matrix initialMatrix(); intmain(){ while (~scanf("%d%d", &n, &l)) { init(); for (int i = 1; i <= n; i++) { scanf("%s", str); insert(str); } buildACAutomaton(); Matrix finalMatrix = isometricSeriesSum(initialMatrix(), l); ull ans = 0; for (int i = 0; i <= tot; i++) { ans += finalMatrix.m[0][i]; } ull totol = isometricSeriesSum(26, l); ans = totol - ans; printf("%llu\n", ans); } } inlinevoidinit(){ memset(trie, 0, sizeof(trie)); memset(fail, 0, sizeof(fail)); tot = 0; memset(permitted, true, sizeof(permitted)); } voidinsert(char s[]){ int len = strlen(s), p = 0; for (int i = 0; i < len; i++) { int ch = s[i] - 'a'; if (!trie[p][ch]) { trie[p][ch] = ++tot; } p = trie[p][ch]; } permitted[p] = false; } voidbuildACAutomaton(){ queue<int>q; for (int i = 0; i < CHARACTER_SET_SIZE; i++) { if (trie[0][i]) { q.push(trie[0][i]); } } while (!q.empty()) { int u = q.front(); q.pop(); //--------------------------------------------- //If the suffix of a string is not allowed //then the string is not allowed //--------------------------------------------- if (!permitted[fail[u]]) { permitted[u] = false; } for (int i = 0; i < CHARACTER_SET_SIZE; i++) { if (trie[u][i]) { fail[trie[u][i]] = trie[fail[u]][i]; q.push(trie[u][i]); } else { trie[u][i] = trie[fail[u]][i]; } } } } Matrix operator*(const Matrix& x, const Matrix& y) { Matrix res; for (int i = 0; i <= tot; i++) { for (int j = 0; j <= tot; j++) { for (int k = 0; k <= tot; k++) { res.m[i][j] += x.m[i][k] * y.m[k][j]; } } } return res; } Matrix operator+(const Matrix& x, const Matrix& y) { Matrix res; for (int i = 0; i <= tot; i++) { for (int j = 0; j <= tot; j++) { res.m[i][j] = x.m[i][j] + y.m[i][j]; } } return res; } Matrix quickPow(Matrix a, int b){ Matrix res; //to construc an identity matrix for (int i = 0; i <= tot; i++) { res.m[i][i] = 1; } while (b) { if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; } ull quickPow(ull a, int b){ ull res = 1; while (b) { if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; } ull isometricSeriesSum(ull a, int n){ if (n == 1) { return a; } ull res = 1; res = res + quickPow(a, n >> 1); res = res * isometricSeriesSum(a, n >> 1); if (n & 1) { res = res + quickPow(a, n); } return res; } Matrix isometricSeriesSum(Matrix a, int n){ if (n == 1) { return a; } Matrix res; for (int i = 0; i <= tot; i++) { res.m[i][i] = 1; } res = res + quickPow(a, n >> 1); res = res * isometricSeriesSum(a, n >> 1); if (n & 1) { res = res + quickPow(a, n); } return res; } Matrix initialMatrix(){ Matrix res; for (int i = 0; i <= tot; i++) { //the node i isn't permitted to reach if (!permitted[i]) { continue; } for (int j = 0; j < CHARACTER_SET_SIZE; j++) { //one of the sons of node i isn't permitted to reach if (!permitted[trie[i][j]]) { continue; } ++res.m[i][trie[i][j]]; } } return res; }