poj 3233 Matrix Power Series （矩阵快速幂+分治）
题意：
Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak.
思路： 对k进行二分。
比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。
以及错误的递归方式：
无形中增加了多少次。。。。。。怎么像小学生呢。。。
正确的写法。。。
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 18 Oct 2016 05:10:53 PM CST
4File Name :code/poj/3233.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=35;
32int n,k,mod;
33struct Mat
34{
35 int mat[N][N];
36 void clear()
37 {
38 ms(mat,0);
39 }
40 void out()
41 {
42 for ( int i = 0 ; i < n ; i++ )
43 {
44 for ( int j = 0 ; j <n-1 ; j++) printf("%d ",mat[i][j]);
45 printf("%d\n",mat[i][n-1]);
46 }
47 }
48}M;
49Mat operator * ( Mat a ,Mat b )
50{
51 Mat c;
52 c.clear();
53 for ( int i = 0 ; i < n ; i++)
54 for ( int j = 0 ; j < n; j ++)
55 for ( int k = 0 ; k < n; k++)
56 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%mod;
57 return c;
58}
59Mat operator + (Mat a,Mat b)
60{
61 Mat c;
62 c.clear();
63 for ( int i = 0 ; i < n ;i ++)
64 for ( int j = 0 ; j < n ; j++)
65 c.mat[i][j] = (a.mat[i][j] + b.mat[i][j])%mod;
66 return c;
67}
68Mat operator ^ (Mat a,int b)
69{
70 Mat c;
71 for ( int i = 0 ; i < n ; i++)
72 for ( int j = 0 ;j <n ; j++)
73 c.mat[i][j] = (i==j);
74 while (b>0)
75 {
76 if (b&1) c = c * a;
77 b = b >> 1;
78 a = a* a;
79 }
80 return c;
81}
82Mat solve( int k)
83{
84 if (k==1) return M;
85 Mat res;
86 res.clear();
87 for ( int i = 0 ; i < n ; i++) res.mat[i][i] = 1;
88 res = res + (M^(k>>1));
89 res = res * solve(k>>1);
90 if (k%2==1) res = res + (M^k);
91 return res;
92}
93int main()
94{
95#ifndef ONLINE_JUDGE
96 freopen("code/in.txt","r",stdin);
97#endif
98 scanf("%d%d%d",&n,&k,&mod);
99 for ( int i = 0 ; i < n ; i++)
100 for ( int j = 0 ; j < n ; j++)
101 scanf("%d",&M.mat[i][j]);
102 Mat ans;
103 ans.clear();
104 ans = solve(k);
105 ans.out();
106#ifndef ONLINE_JUDGE
107 fclose(stdin);
108#endif
109 return 0;
110}