POJ 3233 Matrix Power Series 矩阵快速幂 + 二分

题意：求矩阵的次方和

解题思路：最容易想到方法就是两次二分因为我们可以把一段 A^1 + A^2 + .......A^K 变成 A^1 + ..A^(K/2) +( A^1 + ..A^(K/2))*(A^(k/2)) 当k 为奇数的时候或者 A^1 + ..A^(K/2) +( A^1 + ..A^(K/2))*(A^(k/2)) + A^K 当K 为偶数的时候。

解题代码：

  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 ,m , k ; 
 27 int  ta,tb;
 28 struct Matrix
 29 {
 30    int   mat[30][30];
 31    void clear()
 32    {
 33       memset(mat,0,sizeof(mat));
 34    }
 35    void output()
 36    {
 37      for(int i =0  ;i < n ;i ++)
 38      {
 39        for(int j = 0 ;j < n ;j ++)
 40            printf("%d ",mat[i][j]);
 41      printf("
");
 42      }
 43    }
 44    void init()
 45    {
 46       clear();
 47       for(int i = 0 ;i < n;i ++)
 48           for(int j = 0 ;j < n;j ++)
 49           {
 50             scanf("%d",&mat[i][j]);
 51           }
 52    }
 53    Matrix operator *(const Matrix &b) const
 54    {
 55        Matrix ret;
 56        ret.clear();
 57        for(int i = 0 ;i < n ;i ++)
 58            for(int j = 0;j < n;j ++)
 59            {
 60                for(int s = 0 ;s < n ;s ++)
 61                {
 62                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][s] * b.mat[s][j]) % m ; // 第I 行  第J  列        
 63                }
 64            }
 65        return ret;
 66    }
 67    Matrix operator *(const int  &b) const
 68    {
 69        Matrix ret;
 70        ret.clear();
 71        for(int i = 0 ;i < n ;i ++)
 72            for(int j = 0;j < n;j ++)
 73            {
 74                 ret.mat[i][j] = (mat[i][j] * b) % m ; // 第I 行  第J  列        
 75            }
 76        return ret;
 77    }
 78    Matrix operator +(const Matrix &b) const
 79    {
 80        Matrix ret;
 81        ret.clear();
 82        for(int i = 0 ;i < n ;i ++)
 83            for(int j = 0;j < n;j ++)
 84            {
 85                 ret.mat[i][j] = (mat[i][j] + b.mat[i][j]) % m ; // 第I 行  第J  列        
 86            }
 87        return ret;
 88    }
 89 };
 90 Matrix Pow( Matrix a ,LL t )
 91 {
 92   Matrix ret;
 93   ret.clear();
 94   for(int i = 0 ;i < n ;i ++)
 95        ret.mat[i][i] = 1;
 96   Matrix tmp = a; 
 97   while(t)
 98   {
 99       if(t&1) ret = ret * tmp;
100       tmp = tmp * tmp;
101       t >>=1;
102   }
103   return ret;
104 }
105 Matrix add(Matrix a, int k )
106 {
107     Matrix ans;
108     ans.clear();
109     if(k == 1)
110     {
111       return a;
112     }
113     if(k&1)
114     {
115           Matrix temp = add(a,k/2);
116           ans = temp + temp * Pow(a,k/2) + Pow(a,k);
117     }else{
118           Matrix temp = add(a,k/2);
119           ans = temp + temp * Pow(a,k/2);
120     }
121     return ans ; 
122 }
123 int main(){
124     LL l ;
125     while(scanf("%d %d %d",&n,&k,&m) != EOF)
126     {
127         Matrix  a;
128         a.clear();
129         a.init();
130         a = add(a,k);
131         //a.output();
132         a.output();
133     }
134     return 0;
135 }

View Code

写完以后过了竟然跑了 1300+ms 最快 0ms 不能忍上网查题解发现了这种方法：http://www.cnblogs.com/rainydays/archive/2011/02/21/1960189.html

他的主要思想是多加 n维度构成一个能累加的矩阵，具体看博主题解。

这种思想很巧妙。

没有梦想，何谈远方