搞了4天题，今天终于AC了！！！
这是一道自动机的题，不过要用到矩阵的知识才能完成。所以，在我做这题之前，我先做了poj 3233(n次连续矩阵和)以及poj 2440(状态转移借助矩阵解)作为这题的基础！
题意很简单，就是求长度在1到L中，含有给出字符串的串的个数。直接解是比较难接触答案的，所以要借助反面情况，也就是求不含给出字符串的串的个数。然后用全体情况来减回去，就能得到最终答案了！模2^64，只要稍微有点常识的，都能想到直接用unsigned long long来储存，计算机会自动帮你模的了。
刚开始做的时候，还想直接在建立自动机的时候就把矩阵构建好，结果搞着搞着，发现被我搞乱了。。。囧！所以最后还是把自动机建立好了，再把矩阵搞好！
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 typedef unsigned __int64 ull; 8 9 const int matSize = 30; 10 int curSize = matSize; 11 12 struct Matrix { 13 ull val[matSize][matSize]; 14 15 Matrix(bool ONE = false) { 16 for (int i = 0; i < curSize; i++) { 17 for (int j = 0; j < curSize; j++) { 18 val[i][j] = 0; 19 } 20 val[i][i] = ONE; 21 } 22 } 23 24 void print(int w = curSize, int l = curSize) { 25 for (int i = 0; i < w; i++) { 26 for (int j = 0; j < l; j++) { 27 if (j) putchar(' '); 28 printf("%I64u", val[i][j]); 29 } 30 puts(""); 31 } 32 } 33 } Base, op; 34 35 Matrix operator + (Matrix &_a, Matrix &_b) { 36 Matrix ret; 37 38 for (int i = 0; i < curSize; i++) { 39 for (int j = 0; j < curSize; j++) { 40 ret.val[i][j] = _a.val[i][j] + _b.val[i][j]; 41 } 42 } 43 44 return ret; 45 } 46 47 Matrix operator * (Matrix &_a, Matrix &_b) { 48 Matrix ret = Matrix(); 49 50 for (int i = 0; i < curSize; i++) { 51 for (int k = 0; k < curSize; k++) { 52 if (_a.val[i][k]) { 53 for (int j = 0; j < curSize; j++) { 54 ret.val[i][j] += _a.val[i][k] * _b.val[k][j]; 55 } 56 } 57 } 58 } 59 60 return ret; 61 } 62 63 Matrix operator ^ (Matrix &__a, int _p) { 64 Matrix _a = __a; 65 Matrix ret = Matrix(true); 66 67 while (_p) { 68 if (_p & 1) ret = ret * _a; 69 _a = _a * _a; 70 _p >>= 1; 71 } 72 73 return ret; 74 } 75 76 const int kind = 26; 77 const int maxn = 30; 78 79 int root, cntNode; 80 81 struct Node { 82 int child[kind]; 83 int fail; 84 bool end; 85 86 void init() { 87 for (int i = 0; i < kind; i++) child[i] = -1; 88 fail = -1; 89 end = false; 90 } 91 } node[maxn]; 92 93 int Q[maxn], head, tail; 94 95 void init() { 96 root = cntNode = 0; 97 node[root].init(); 98 } 99 100 void insert(char *_s) {101 int _p = root, index;102 103 while (*_s) {104 index = *_s - 'a';105 if (node[_p].child[index] == -1) {106 node[++cntNode].init();107 node[_p].child[index] = cntNode;108 }109 _p = node[_p].child[index];110 _s++;111 }112 node[_p].end = true;113 }114 115 void buildMat() {116 op = Matrix();117 Base = Matrix();118 Base.val[0][0] = 1;119 120 head = tail = 0;121 Q[tail++] = root;122 123 while (head < tail) {124 int u = Q[head++];125 126 for (int i = 0; i < kind; i++) {127 int c = node[u].child[i];128 129 if (~c) {130 if (u == root) {131 node[c].fail = root;132 } else {133 node[c].fail = node[node[u].fail].child[i];134 if (node[node[c].fail].end) node[c].end = true;135 }136 Q[tail++] = c;137 } else {138 if (u == root) {139 node[u].child[i] = root;140 } else {141 node[u].child[i] = node[node[u].fail].child[i];142 }143 }144 }145 }146 147 for (int i = 0; i < curSize; i++) {148 if (node[i].end) continue;149 150 for (int j = 0; j < kind; j++) {151 int t = node[i].child[j];152 153 if (node[t].end) continue;154 op.val[i][t]++;155 }156 }157 158 // for (int i = 0; i <= cntNode; i++) {159 // printf("%d : fail %d ", i, node[i].fail);160 // for (int j = 0; j < kind; j++) {161 // printf(" %d", node[i].child[j]);162 // }163 // puts("");164 // }165 // op.print();166 }167 168 Matrix calSum(Matrix &_mat, int _p) {169 Matrix ONE = Matrix(true), ep = _mat;170 Matrix ret = Matrix(), cur = Matrix(true), tmp;171 172 while (_p) {173 if (_p & 1) {174 ret = ret * ep;175 ret = ret + cur;176 }177 tmp = ONE + ep;178 cur = cur * tmp;179 ep = ep * ep;180 _p >>= 1;181 }182 ret = ret * _mat;183 184 return ret;185 }186 187 ull cal(int _p) {188 ull sum = 0;189 190 // op.print();191 op = calSum(op, _p);192 Base = Base * op;193 // puts("Base:");194 // Base.print();195 196 op = Matrix();197 op.val[0][0] = 26;198 op = calSum(op, _p);199 // puts("op:");200 // op.print();201 202 for (int i = 0; i < curSize; i++) {203 sum += op.val[0][i];204 sum -= Base.val[0][i];205 }206 207 return sum;208 }209 210 int main() {211 int n, l;212 char buf[10];213 214 // freopen("in", "r", stdin);215 while (~scanf("%d%d", &n, &l)) {216 init();217 while (n--) {218 scanf("%s", buf);219 insert(buf);220 }221 curSize = cntNode + 1;222 buildMat();223 printf("%I64u\n", cal(l));224 }225 226 return 0;227 }
——written by Lyon