POJ3233Matrix Power Series（十大矩阵问题之三 + 二分+矩阵快速幂）

Matrix Power Series

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 18658		Accepted: 7895

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

Source

POJ Monthly--2007.06.03, Huang, Jinsong

当n为奇数；假设 n = 7: A + A ^ 2 + A ^ 3 + A ^ 4 + A ^ 5 + A ^ 6 + A＾７ = A + A ^ 2 + A ^ 3 + A ^ 3 * (A + A ^ 2 + A ^ 3) + A ^ 7

当n为偶数的时候就简单了

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 int n,m,k;
 8 struct Mat
 9 {
10     int mat[35][35];
11 };
12 Mat operator* (Mat x, Mat y)
13 {
14     Mat c;
15     memset(c.mat, 0, sizeof(c.mat));
16     for(int t = 1; t <= n; t++)
17     {
18         for(int i = 1; i <= n; i++)
19         {
20             for(int j = 1; j <= n; j++)
21                 c.mat[i][j] = (c.mat[i][j] + x.mat[i][t] % m * (y.mat[t][j] % m) ) % m;
22         }
23     }
24     return c;
25 }
26 Mat operator^ (Mat x, int y)
27 {
28     Mat c;
29     for(int i = 1; i <= n; i++)
30         for(int j = 1; j <= n; j++)
31             c.mat[i][j] = (i == j);
32     while(y)
33     {
34         if(y & 1)
35             c = c * x;
36         x = x * x;
37         y >>= 1;
38     }
39     return c;
40 }
41 Mat operator + (Mat x, Mat y)
42 {
43     for(int i = 1; i <= n; i++)
44     {
45         for(int j = 1; j <= n; j++)
46             x.mat[i][j] = ( x.mat[i][j] % m + y.mat[i][j] % m ) % m;
47     }
48     return x;
49 }
50 Mat dfs(int t,Mat temp)
51 {
52     if(t == 1)
53         return temp;
54     int mid = t / 2;
55     Mat c = dfs(mid, temp);
56     if(t & 1)
57     {
58        c = c + (temp ^ mid ) * c;
59        return c + (temp ^ t); //第一次交没加括号，查了好长时间的错，惭愧惭愧，其实codeblock都waring了，弱
60     }
61     else
62         return c + (temp ^ mid) * c;
63 }
64 int main()
65 {
66 
67     scanf("%d%d%d", &n,&k,&m);
68     Mat a,c;
69     for(int i = 1; i <= n; i++)
70         for(int j = 1; j <= n; j++)
71             scanf("%d", &a.mat[i][j]);
72     c = dfs(k,a);
73     for(int i = 1; i <= n; i++)
74     {
75         for(int j = 1; j < n; j++)
76             printf("%d ", c.mat[i][j]);
77         printf("%d
", c.mat[i][n]);
78     }
79     return 0;
80 }

View Code