【HDU】2243 考研路茫茫――单词情结

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define MAXN 26
  5 #define MOD 10330176681277348905LL
  6 typedef unsigned long long LL;
  7 using namespace std;
  8 char str[MAXN];
  9 int size;
 10 LL total, ans;
 11 struct node {
 12     int fail, next[MAXN];
 13     bool end;
 14     void Init() {
 15         end = false;
 16         fail = 0;
 17         memset(next, 0, sizeof(next));
 18     }
 19 };
 20 struct Matrix {
 21     LL mat[MAXN][MAXN];
 22     void Zero() {
 23         memset(mat, 0, sizeof(mat));
 24     }
 25     void Unit() {
 26         int i;
 27         for (i = 0; i <= size; i++)
 28             mat[i][i] = 1;
 29     }
 30 };
 31 Matrix a, b;
 32 node tree[MAXN];
 33 Matrix operator +(const Matrix &a, const Matrix &b) {
 34     int i, j;
 35     Matrix temp;
 36     temp.Zero();
 37     for (i = 0; i <= size; i++) {
 38         for (j = 0; j <= size; j++)
 39             temp.mat[i][j] = a.mat[i][j] + b.mat[i][j];
 40     }
 41     return temp;
 42 }
 43 Matrix operator *(const Matrix &a, const Matrix &b) {
 44     int i, j, k;
 45     Matrix temp;
 46     temp.Zero();
 47     for (i = 0; i <= size; i++) {
 48         for (j = 0; j <= size; j++) {
 49             for (k = 0; k <= size; k++)
 50                 temp.mat[i][j] += a.mat[i][k] * b.mat[k][j];
 51         }
 52     }
 53     return temp;
 54 }
 55 Matrix operator ^(Matrix x, int k) {
 56     Matrix temp;
 57     temp.Zero();
 58     temp.Unit();
 59     for (; k; k >>= 1) {
 60         if (k & 1)
 61             temp = temp * x;
 62         x = x * x;
 63     }
 64     return temp;
 65 }
 66 inline int GET(char ch) {
 67     return ch - 'a';
 68 }
 69 void Insert(char *s) {
 70     int now, t;
 71     for (now = 0; *s; s++) {
 72         t = GET(*s);
 73         if (!tree[now].next[t]) {
 74             tree[++size].Init();
 75             tree[now].next[t] = size;
 76         }
 77         now = tree[now].next[t];
 78     }
 79     tree[now].end = true;
 80 }
 81 void BFS() {
 82     int now, i, p;
 83     queue<int> q;
 84     q.push(0);
 85     while (!q.empty()) {
 86         now = q.front();
 87         q.pop();
 88         for (i = 0; i < MAXN; i++) {
 89             if (tree[now].next[i]) {
 90                 p = tree[now].next[i];
 91                 if (now)
 92                     tree[p].fail = tree[tree[now].fail].next[i];
 93                 tree[p].end |= tree[tree[p].fail].end;
 94                 q.push(p);
 95             } else
 96                 tree[now].next[i] = tree[tree[now].fail].next[i];
 97         }
 98     }
 99 }
100 void GetTotal(int k) {
101     LL temp;
102     total = 1;
103     for (temp = 26; k; k >>= 1) {
104         if (k & 1)
105             total *= temp;
106         temp *= temp;
107     }
108     total = 26 * (total - 1) * MOD;
109 }
110 void Build() {
111     int i, j, p;
112     a.Zero();
113     for (i = 0; i <= size; i++) {
114         if (!tree[i].end) {
115             for (j = 0; j < MAXN; j++) {
116                 p = tree[i].next[j];
117                 if (p) {
118                     if (!tree[p].end)
119                         a.mat[i][p]++;
120                 } else
121                     a.mat[i][0]++;
122             }
123         }
124     }
125 }
126 Matrix DFS(int k) {
127     if (k == 1)
128         return a;
129     if (k & 1)
130         return DFS(k - 1) + (a ^ k);
131     else {
132         Matrix temp = DFS(k >> 1);
133         return temp + ((a ^ (k >> 1)) * temp);
134     }
135 }
136 int main() {
137     int n, m, i;
138     while (~scanf("%d%d", &n, &m)) {
139         GetTotal(m);
140         tree[0].Init();
141         for (i = size = 0; i < n; i++) {
142             scanf(" %s", str);
143             Insert(str);
144         }
145         BFS();
146         Build();
147         b = DFS(m);
148         for (ans = i = 0; i <= size; i++)
149             ans += b.mat[0][i];
150         printf("%I64u\n", total - ans);
151     }
152     return 0;
153 }