本文共 3589 字，大约阅读时间需要 11 分钟。
跟上一篇一样，都是自动机加矩阵的题。不过这次因为忘记将答案取模了，所以wa了一次。。。- -这次的代码相对整齐了点，没有上一篇那么乱了。。。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 const int matSize = 105; 11 const int initMod = 100000; 12 int curSize = matSize; 13 typedef long long ll; 14 15 struct Matrix { 16 ll val[matSize][matSize]; 17 18 Matrix (bool ONE = false) { 19 for (int i = 0; i < curSize; i++) { 20 for (int j = 0; j < curSize; j++) { 21 val[i][j] = 0; 22 } 23 val[i][i] = ONE; 24 } 25 } 26 27 void print(int _l = curSize, int _w = curSize) { 28 for (int i = 0; i < _l; i++) { 29 for (int j = 0; j < _w; j++) { 30 if (j) putchar(' '); 31 cout << val[i][j]; 32 } 33 puts(""); 34 } 35 } 36 } Base, op; 37 38 Matrix operator * (Matrix &_a, Matrix &_b) { 39 Matrix ret = Matrix(); 40 41 for (int i = 0; i < curSize; i++) { 42 for (int k = 0; k < curSize; k++) { 43 if (_a.val[i][k]) { 44 for (int j = 0; j < curSize; j++) { 45 ret.val[i][j] += _a.val[i][k] * _b.val[k][j]; 46 ret.val[i][j] %= initMod; 47 } 48 } 49 } 50 } 51 52 return ret; 53 } 54 55 Matrix operator ^ (Matrix &__a, ll _p) { 56 Matrix _a = __a; 57 Matrix ret = Matrix(true); 58 59 while (_p) { 60 if (_p & 1) { 61 ret = ret * _a; 62 } 63 _a = _a * _a; 64 _p >>= 1; 65 } 66 67 return ret; 68 } 69 70 const int maxNode = 105; 71 const int kind = 4; 72 int root, cntNode; 73 int Q[maxNode], qh, qt; 74 75 struct Node { 76 int child[kind]; 77 int fail; 78 bool end; 79 80 Node() { 81 for (int i = 0; i < kind; i++) { 82 child[i] = -1; 83 } 84 fail = -1; 85 end = false; 86 } 87 } node[maxNode]; 88 89 map con; 90 91 void init() { 92 con.clear(); 93 con['A'] = 0; 94 con['T'] = 1; 95 con['C'] = 2; 96 con['G'] = 3; 97 } 98 99 void initTrie() {100 root = 0;101 cntNode = 1;102 node[root] = Node();103 }104 105 void insert(char *_s) {106 int cur = root;107 108 while (*_s) {109 int index = con[*_s];110 111 if (node[cur].child[index] == -1) {112 node[cur].child[index] = cntNode;113 node[cntNode] = Node();114 cntNode++;115 }116 cur = node[cur].child[index];117 _s++;118 }119 node[cur].end = true;120 }121 122 void buildMat() {123 Base = Matrix();124 op = Matrix();125 Base.val[0][0] = 1;126 127 qh = qt = 0;128 Q[qt++] = root;129 node[root].fail = root;130 131 while (qh < qt) {132 int cur = Q[qh++];133 134 for (int i = 0; i < kind; i++) {135 int c = node[cur].child[i];136 137 if (~c) {138 if (cur == root) {139 node[c].fail = root;140 } else {141 node[c].fail = node[node[cur].fail].child[i];142 if (node[node[c].fail].end) node[c].end = true;143 }144 Q[qt++] = c;145 } else {146 if (cur == root) {147 node[cur].child[i] = root;148 } else {149 node[cur].child[i] = node[node[cur].fail].child[i];150 }151 }152 }153 }154 155 for (int i = 0; i < cntNode; i++) {156 if (node[i].end) continue;157 158 for (int j = 0; j < kind; j++) {159 if (node[node[i].child[j]].end) continue;160 op.val[i][node[i].child[j]]++;161 }162 }163 164 // op.print();165 }166 167 int main() {168 int n, m;169 170 // freopen("in", "r", stdin);171 init();172 while (cin >> n >> m) {173 char buf[15];174 175 initTrie();176 while (n--) {177 cin >> buf;178 insert(buf);179 // puts("Inserted");180 }181 curSize = cntNode;182 buildMat();183 op = op ^ m;184 Base = Base * op;185 186 ll ans = 0;187 188 for (int i = 0; i < curSize; i++) {189 ans += op.val[0][i];190 }191 cout << ans % initMod<< endl;192 }193 194 return 0;195 }
——written by Lyon
转载于:https://www.cnblogs.com/LyonLys/archive/2012/10/05/poj_2778_Lyon.html
View Code