POJ: Matrix Power Series

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + 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

Problem Analysis:

If we iterate computing the item of the polynomial, the time complexity is O(n³k). Let’s optimize it.

Suppose S(k) = I + A + A² + … + A^{k-1}, then

So we can use the matrix to get the time complexity O(n³ logk)

Solution

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, m;
vector<vector<int> > multiple(vector<vector<int> >& a, vector<vector<int> >& b) {
  vector<vector<int> > res(a.size(), vector<int>(a[0].size(), 0));
  for (int i = 0; i < a.size(); ++i) {
    for (int j = 0; j < a[0].size(); ++j) {
      for (int k = 0; k < a.size(); ++k) {
        res[i][j] += a[i][k] * b[k][j];
        res[i][j] %= m;
      }
    }
  }
  return res;
}
int main(int argc, char *argv[]) {
  scanf("%d%d%d", &n, &k, &m);
  
  vector<vector<int> > matrix(n * 2, vector<int>(n * 2, 0));
  vector<vector<int> > pn(n * 2, vector<int>(n * 2, 0));
  for (int i = 0; i < n; ++i) {
    getchar();
    for (int j = 0; j < n; ++j) {
      scanf("%d", &matrix[i][j]);
      matrix[i][j] %= m;
      pn[i][j] = matrix[i][j];
    }
    matrix[i + n][i] = 1;
    matrix[i + n][n + i] = 1;
  }
  for (int i = 0; i < 2 * n; ++i) pn[i][i] = 1;
  ++k;
  while (k > 0) {
    if (k & 1) pn = multiple(pn, matrix);
    matrix = multiple(matrix, matrix);
    k >>= 1;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) pn[i + n][j] = (pn[i + n][j] + m - 1) % m;
      printf("%d%c", pn[i + n][j], (j == n - 1) ? '\n' : ' ');
    }
  }
  return 0;
}

time complexity is O(n³ logk)

space complexity is O(n²)