HDU 2604 Queuing 矩阵快速幂

题意：给你一个01串，为你长度为 n且不包含 010,000,这两个串的情况有多少种。

解题思路：

首先我们假设前把前两个字母的情况列出来

只有4种

00（1） 10（2）

01 （3） 11 （4）

假设我们dp 到了下一个字母

显然，（4）状态只能由（3）（4）转移过来

（3）状态只能由（2）（1）转移过来

（2）只能右（4）转移过来

（1）只能由（2）转移过来

如果暴力做的话会超时。。所以我们应该能想到这题是用矩阵快速幂做的，我最开始想到的就是用 2x2 的矩阵去维护，但

是显然状态很难推，所以我们把我们的初始矩阵变为 4 x 1（都是用一维矩阵保存状态，二维太过繁琐），这样就可以很快的

构造出中间矩阵了。

转载一张图：http://www.cnblogs.com/zfyouxi/p/3774402.html

、

解题代码：

  1 // File Name: temp.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年09月17日 星期三 11时35分45秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 using namespace std;
 26 int n , k,l ,m; 
 27 struct Matrix
 28 {
 29    int  mat[20][20];
 30    void clear()
 31    {
 32       memset(mat,0,sizeof(mat));
 33    }
 34    void output()
 35    {
 36      for(int i =0  ;i < n ;i ++)
 37      {
 38        for(int j = 0 ;j < n ;j ++)
 39            printf("%d ",mat[i][j]);
 40      printf("
");
 41      }
 42    }
 43    void init()
 44    {
 45        n = 4;
 46        clear();
 47        mat[0][0] = 1; 
 48        mat[0][3] = 1;
 49        mat[1][2] = 1;
 50        mat[2][0] = 1;
 51        mat[3][1] = 1;
 52        mat[3][2] = 1;
 53    }
 54    Matrix operator *(const Matrix &b) const
 55    {
 56        Matrix ret;
 57        ret.clear();
 58        for(int i = 0 ;i < n ;i ++)
 59            for(int j = 0;j < n;j ++)
 60            {
 61                for(int k = 0 ;k < n ;k ++)
 62                {
 63                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行  第J  列        
 64                }
 65            }
 66        return ret;
 67    }
 68 };
 69 Matrix Pow( Matrix a ,int t )
 70 {
 71   Matrix ret;
 72   ret.clear();
 73   for(int i = 0 ;i < n ;i ++)
 74        ret.mat[i][i] = 1;
 75   Matrix tmp = a; 
 76   while(t)
 77   {
 78       if(t&1) ret = ret * tmp;
 79       tmp = tmp * tmp;
 80       t >>=1;
 81   }
 82   return ret;
 83 }
 84 int main(){
 85     while(scanf("%d %d",&l,&m) != EOF)
 86     {
 87         if(l  == 1 )
 88         {
 89             printf("2
");
 90             continue;
 91         }
 92         if(l == 2)
 93         {
 94             printf("4
");
 95             continue;
 96         }
 97         Matrix  a;
 98         a.init();
 99         a = Pow(a,l-2);
100         int sum = 0 ; 
101         for(int i = 0 ;i < n;i ++)
102             for(int j =0 ;j < 4;j ++)
103             {
104               sum += a.mat[i][j];
105             }
106         sum %= m;
107         printf("%d
",sum);
108     }
109     return 0;
110 }

View Code

没有梦想，何谈远方