首先对2^64取模的话,可以直接用unsigned long long,这样溢出部分就是取模后的结果了 方法类似POJ2778传送门 只不过这里要统计长度不超过m的方案 我们先统计出长度为m的所有方案,然后减去不包含这些串的方案,剩下就是至少包含一个串的方案了 设转移矩阵为A 相当于sum = A + A^2 + … A^m f(m) = f(m / 2) * (1 + A ^(m / 2)) + (m & 1) ? A^m : 0 二分即可求出,但是不要写成递归的,不然会爆栈
对于求总数 f(m) = 1 + 26 + … + 26^m f(m) = f(m – 1) * 26 + 1 [f(m), 1] = [26, 1; 0 1][f(m – 1), 1]; 转移即可
/*************************************************************************> File Name: hdu2243.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年03月11日 星期三 10时27分24秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int MAX_NODE = 26;const int CHILD_NUM = 26;struct node{int k;mat[MAX_NODE][MAX_NODE];void clear(){memset (mat, 0, sizeof(mat));}};stack <node> st;struct MARTIX{mat[MAX_NODE][MAX_NODE];}A, E;MARTIX mul(MARTIX a, MARTIX b, int L){MARTIX c;for (int i = 0; i < L; ++i){for (int j = 0; j < L; ++j){c.mat[i][j] = 0;for (int k = 0; k < L; ++k){c.mat[i][j] += a.mat[i][k] * b.mat[k][j];}}}return c;}MARTIX add(MARTIX a, MARTIX b, int L){for (int i = 0; i < L; ++i){for (int j = 0; j < L; ++j){a.mat[i][j] += b.mat[i][j];}}return a;}MARTIX martix_pow(MARTIX ret, int n, int L){MARTIX ans;for (int i = 0; i < L; ++i){for (int j = 0; j < L; ++j){ans.mat[i][j] = (i == j);}}while (n){if (n & 1){ans = mul(ans, ret, L);}n >>= 1;ret = mul(ret, ret, L);}return ans;}/*MARTIX Binsearch(int k, int L){if (k == 1){return A;}if (k & 1){MARTIX a = martix_pow(A, k >> 1, L);a = add(a, E, L);MARTIX b = Binsearch(k >> 1, L);a = mul(a, b, L);MARTIX c = martix_pow(A, k, L);a = add(a, c, L);return a;}else{MARTIX a = martix_pow(A, k >> 1, L);a = add(a, E, L);MARTIX b = Binsearch(k >> 1, L);a = mul(a, b, L);return a;}}*/MARTIX work (int k, int L){while (!st.empty()){st.pop();}int tmp = k;while (tmp != 1){node x;x.clear();x.k = tmp;st.push(x);tmp >>= 1;}MARTIX ans = A;while (!st.empty()){node cur = st.top();st.pop();MARTIX a = martix_pow(A, cur.k / 2, L);a = add(a, E, L);ans = mul(ans, a, L);if (cur.k & 1){MARTIX b = martix_pow(A, cur.k, L);ans = add(ans, b, L);}}return ans;}struct AC_Automation{int next[MAX_NODE][CHILD_NUM];int fail[MAX_NODE];int end[MAX_NODE];int root, L;int newnode(){for (int i = 0; i < CHILD_NUM; ++i){next[L][i] = -1;}end[L++] = 0;return L – 1;}void init(){L = 0;root = newnode();}void Build_Trie(char buf[]){int len = strlen(buf);int now = root;for (int i = 0; i < len; ++i){if (next[now][buf[i] – ‘a’] == -1){next[now][buf[i] – ‘a’] = newnode();}now = next[now][buf[i] – ‘a’];}end[now] = 1;}void Build_AC(){queue <int> qu;fail[root] = root;for (int i = 0; i < CHILD_NUM; ++i){if (next[root][i] == -1){next[root][i] = root;}else{fail[next[root][i]] = root;qu.push(next[root][i]);}}while (!qu.empty()){int now = qu.front();qu.pop();if (end[fail[now]]){end[now] = 1;}for (int i = 0; i < CHILD_NUM; ++i){if (next[now][i] == -1){next[now][i] = next[fail[now]][i];}else{fail[next[now][i]] = next[fail[now]][i];qu.push(next[now][i]);}}}}void solve (int n){ans = 0;MARTIX tmp;tmp.mat[0][0] = 26;tmp.mat[0][1] = 1;tmp.mat[1][0] = 0;tmp.mat[1][1] = 1;tmp = martix_pow(tmp, n, 2);ans = tmp.mat[0][0] + tmp.mat[0][1] – 1;for (int i = 0; i < L; ++i){for (int j = 0; j < L; ++j){A.mat[i][j] = 0;E.mat[i][j] = (i == j);}}for (int i = 0; i < L; ++i){if (end[i]){continue;}for (int j = 0; j < CHILD_NUM; ++j){if (!end[next[i][j]]){++A.mat[i][next[i][j]];}}}MARTIX res = work(n, L);for (int i = 0; i < L; ++i){ans -= res.mat[0][i];}printf(“%llu\n”, ans);}}AC;char buf[15];int main(){int m, n;while (~scanf(“%d%d”, &m, &n)){AC.init();for (int i = 1; i <= m; ++i){scanf(“%s”, buf);AC.Build_Trie(buf);}AC.Build_AC();AC.solve(n);}return 0;}
，生活若剥去了理想梦想幻想，那生命便只是一堆空架子
