poj 2440 DNA (mid)

　　题意是给出两种串，要求计算长度为L的，而且不含那两种子串的串的个数。

　　这个的做法主要是要靠状态转移，而且明白转移的技巧做这题就如鱼得水，轻松过了！长度为3的01串也就8种状态，如果我们把它编号了，以后添加一位的时候，根据最后三位，我们就可以从之前的装态将已统计的个数转移到现在当前这一层来。例如，0可以由0或4转移过来。

　　然后就可以简单的构造出矩阵来了！

代码如下：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cassert>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int maxSize = 8;
 9 const int initMod = 2E3 + 5;
10 int curSize = maxSize;
11 int curMod = initMod;
12 
13 struct Matrix {
14     int val[maxSize][maxSize];
15 
16     Matrix(bool ONE = false) {
17         for (int i = 0; i < curSize; i++) {
18             for (int j = 0; j < curSize; j++) {
19                 val[i][j] = 0;
20             }
21             if (ONE) val[i][i] = 1;
22         }
23     }
24 
25     void print(int _l = curSize, int _w = curSize) {
26         for (int i = 0; i < _l; i++) {
27             for (int j = 0; j < _w; j++) {
28                 if (j) putchar(' ');
29                 printf("%d", val[i][j]);
30             }
31             puts("");
32         }
33         puts("~~");
34     }
35 };
36 
37 Matrix operator * (Matrix &_a, Matrix &_b) {
38     Matrix ret = Matrix();
39 
40     for (int i = 0; i < curSize; i++) {
41         for (int k = 0; k < curSize; k++) {
42             if (_a.val[i][k]) {
43                 for (int j = 0; j < curSize; j++) {
44                     ret.val[i][j] += _a.val[i][k] * _b.val[k][j];
45                     ret.val[i][j] %= curMod;
46                 }
47             }
48         }
49     }
50 
51     return ret;
52 }
53 
54 Matrix operator ^ (Matrix &_a, int _p) {
55     Matrix __a = _a, ret = Matrix(true);
56 
57     while (_p) {
58         if (_p & 1) {
59             ret = ret * __a;
60         }
61         __a = __a * __a;
62         _p >>= 1;
63     }
64 
65     return ret;
66 }
67 
68 int deal(int _n) {
69     Matrix Base = Matrix(), op = Matrix();
70 
71     Base.val[0][0] = Base.val[0][1] = 1;
72     for (int i = 0; i < 4; i++) {
73         op.val[i][i << 1] = op.val[i + 4][i << 1] = 1;
74         if (i != 2 && i != 3) op.val[i][i << 1 | 1] = op.val[i + 4][i << 1 | 1] = 1;
75     }
76     op = op ^ (_n - 1);
77     Base = Base * op;
78 //    Base.print();
79 //    op.print();
80 
81     int sum = 0;
82 
83     for (int i = 0; i < 8; i++) sum += Base.val[0][i], sum %= curMod;
84 
85     return sum;
86 }
87 
88 int main() {
89     int n;
90 
91     while (~scanf("%d", &n)) printf("%d\n", deal(n));
92 
93     return 0;
94 }

　　hdu 2243的自动机的题跟这个差不多，应该也是这样先找到所有可行的串，然后再用所有情况减去。。。

——written by Lyon