Matrix Power Series
Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). 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
题目类型：矩阵快速幂 + 二分
算法分析：直接计算每一个矩阵的幂然后求和取模会TLE，此时考虑到A ^ 1 + A ^ 2 + A ^ 3 + A ^ 4 = (A ^ 1 + A ^ 2) + (A ^ 1 + A ^ 2) * A ^ 2，可以使用二分的思想先将A ^ 1 + A ^ 2 + ……A ^ n划分成{A ^ 1 + A ^ 2 + A ^ (k / 2)} + A ^(k / 2)] + {A ^ (k / 2 + 1) + A ^ + ……A ^ n}三部分，由于第三部分可以由第一部分每一项乘以A ^ (k / 2)得到，所以可以先计算出第一部分，再直接乘方求和
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int MOD = 10000; const int maxn = 36 + 6; struct Mat { int mat[maxn][maxn]; }; int n, k, mod; Mat A, ans; Mat operator * (Mat a, Mat b) { Mat c; memset (c.mat, 0, sizeof (c.mat)); int i, j, k; for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { if (a.mat[i][k] == 0) continue; for (j = 0; j < n; j++) { if (b.mat[k][j] == 0) continue; c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % mod) % mod; } } } return c; } Mat operator ^ (Mat a, int k) { Mat c; int i, j; for (i = 0; i < n; i++) for(j = 0; j < n; j++) c.mat[i][j] = (i == j); while (k) { if(k & 1) c = c * a; a = a * a; k >>= 1; } return c; } Mat operator + (Mat a, Mat b) { Mat c; int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { c.mat[i][j] = ((a.mat[i][j] % mod) + (b.mat[i][j] % mod)) % mod; } } return c; } Mat MatrixSum (int k) { if (k == 1) return A; Mat temp, b; temp = MatrixSum (k / 2); if (k & 1) { b = A ^ (k / 2 + 1); temp = temp + (temp * b); temp = temp + b; } else { b = A ^ (k / 2); temp = temp + (temp * b); } return temp; } int main() { // freopen ("aaa.txt", "r", stdin); scanf ("%d%d%d", &n, &k, &mod); int i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf ("%d", &A.mat[i][j]); ans = MatrixSum (k); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (j == 0) cout << ans.mat[i][j]; else cout << " " << ans.mat[i][j]; } cout << endl; } return 0; } |
- « 上一篇：poj3126
- poj3243：下一篇 »