题意是给出两种串，要求计算长度为L的，而且不含那两种子串的串的个数。
这个的做法主要是要靠状态转移，而且明白转移的技巧做这题就如鱼得水，轻松过了！长度为3的01串也就8种状态，如果我们把它编号了，以后添加一位的时候，根据最后三位，我们就可以从之前的装态将已统计的个数转移到现在当前这一层来。例如，0可以由0或4转移过来。
然后就可以简单的构造出矩阵来了！
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 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