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
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<queue> #include<bitset> #include<ctime> #include<string> #include<iomanip> #include<algorithm> using namespace std; #define INT __int64 const int INF = 0x3f3f3f3f; const double esp = 0.00000001; const double PI = acos(-1.0); const int MY = 8; const int MX = 30 + 5; INT n, k, mod; struct M { INT p[MX][MX]; void zero() { memset(p, 0, sizeof(p)); } void unit() { for (int i = 0; i < n; ++i) p[i][i] = 1; } }ans; M operator + (const M& a, const M& b) { M c; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) c.p[i][j] = (a.p[i][j] + b.p[i][j]) % mod; return c; } M operator * (const M& a, const M& b) { M c; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { c.p[i][j] = 0; for (int q = 0; q < n; ++q) c.p[i][j] += (a.p[i][q] * b.p[q][j]) % mod; } return c; } M operator ^ (M a, INT k) { M b; b.zero(); b.unit(); while (k) { if (k & 1) b = b * a; a = a * a; k >>= 1; } return b; } M sum(INT k) { if (k == 1) return ans; else { M t = sum(k / 2); if (k & 1) { M b = ans ^ ((k >> 1) + 1); return t + b + t * b; } else { M b = ans ^ (k >> 1); return t + t * b; } } } int main() { while (~scanf("%I64d%I64d%I64d", &n, &k, &mod)) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { scanf("%I64d", &ans.p[i][j]); ans.p[i][j] %= mod; } M c = sum(k); for (int i = 0; i < n; ++i) { cout << c.p[i][0] % mod; for (int j = 1; j < n; ++j) cout << " " << c.p[i][j] % mod; cout << endl; } } return 0; }