UVA11149 Power of Matrix —— 矩阵倍增、矩阵快速幂

题目链接：https://vjudge.net/problem/UVA-11149

题意：

给出矩阵A，求出A^1 + A^2 …… + A^k 。

题解：

1.可知：A^1 + A^2 …… + A^k = （1+A^k/2）*（A^1 + A^2 …… + A^k/2）+ （k%2?A^k：0）。

2.根据上述式子，可二分对其求解。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 //const int MOD = 1e9+7;
17 const int MAXN = 1e6+100;
18 
19 const int MOD = 10;
20 int Size;
21 struct MA
22 {
23     LL mat[45][45];
24     void init()
25     {
26         for(int i = 0; i<Size; i++)
27         for(int j = 0; j<Size; j++)
28             mat[i][j] = (i==j);
29     }
30 };
31 
32 MA mul(MA x, MA y)
33 {
34     MA ret;
35     memset(ret.mat, 0, sizeof(ret.mat));
36     for(int i = 0; i<Size; i++)
37     for(int j = 0; j<Size; j++)
38     for(int k = 0; k<Size; k++)
39         ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j]%MOD, ret.mat[i][j] %= MOD;;
40     return ret;
41 }
42 
43 MA add(MA x, MA y)
44 {
45     MA ret;
46     memset(ret.mat, 0, sizeof(ret.mat));
47     for(int i = 0; i<Size; i++)
48     for(int j = 0; j<Size; j++)
49         ret.mat[i][j] = x.mat[i][j]+y.mat[i][j], ret.mat[i][j] %= MOD;
50     return ret;
51 }
52 
53 MA qpow(MA x, LL y)
54 {
55     MA s;
56     s.init();
57     while(y)
58     {
59         if(y&1) s = mul(s, x);
60         x = mul(x, x);
61         y >>= 1;
62     }
63     return s;
64 }
65 
66 MA solve(MA x, int k)
67 {
68     if(k==1) return x;
69     MA s;
70     s.init();
71     s = mul(add(s, qpow(x, k/2)), solve(x, k/2));
72     if(k%2) s = add(s, qpow(x, k));
73     return s;
74 }
75 
76 int main()
77 {
78     int n, k;
79     while(scanf("%d%d", &n,&k)&&n)
80     {
81         MA s;
82         Size = n;
83         memset(s.mat, 0, sizeof(s.mat));
84         for(int i = 0; i<n; i++)
85         for(int j = 0; j<n; j++)
86         {
87             scanf("%lld", &s.mat[i][j]);
88             s.mat[i][j] %= MOD;
89         }
90 
91         s = solve(s, k);
92         for(int i = 0; i<n; i++)
93         {
94             for(int j = 0; j<n; j++)
95                 printf("%lld%s", s.mat[i][j], j==n-1?"
":" ");
96         }
97         printf("
");
98     }
99 }

View Code