记录编号	601273	评测结果	AAAAAAAAAA
题目名称	2481.[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	3.263 s
提交时间	2025-06-07 18:51:50	内存使用	2.05 MiB

#include <cstdio>
#include <cstring>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
typedef __int128 int128;
typedef long long ll;

template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0) putchar('-'), x = -x;
  static int sta[128], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAX_SIZE = 31;
int128 MOD;

struct Matrix {
  int n, m;
  int128 a[MAX_SIZE << 1][MAX_SIZE << 1];

  Matrix () {
    memset(a, 0, sizeof a);
  }
  Matrix (int n, int m, bool flag = false) : n(n), m(m) {
    memset(a, 0, sizeof a);
    if (flag) {
      for (int i = 1; i <= n; ++i) {
        a[i][i] = 1;
      }
    }
  }

  int128* operator [](int val) {
    return a[val];
  }
  void print() {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        write(a[i][j], " \n"[j == m]);
      }
    }
  }
};

Matrix operator * (Matrix x, Matrix y) {
  Matrix res(x.n, y.m);
  for (int k = 1; k <= x.m; ++k) {
    for (int i = 1; i <= x.n; ++i) {
      for (int j = 1; j <= y.m; ++j) {
        res[i][j] = (res[i][j] + x[i][k] * y[k][j] % MOD) % MOD;
      }
    }
  }
  return res;
}

Matrix kasumi(Matrix x, ll y) {
  Matrix res(x.n, x.m, true);
  while (y) {
    if (y & 1) res = res * x;
    y >>= 1;
    x = x * x;
  }
  return res;
}

int n;
ll k;

int main() {
  freopen("matrix_sum.in", "r", stdin);
  freopen("matrix_sum.out", "w", stdout);
  n = read<int>(), k = read<ll>(), MOD = read<int128>();

  Matrix E(n, n, true), O(n, n), A(n, n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      A[i][j] = read<int128>();
    }
  }

  Matrix X(n << 1, n << 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      X[i][j] = A[i][j];
      X[i][j + n] = E[i][j];
      X[i + n][j] = O[i][j];
      X[i + n][j + n] = E[i][j];
    }
  }

  X = kasumi(X, k + 1);
  for (int i = 1; i <= n; ++i) {
    X[i][i + n] = ((X[i][i + n] - 1) % MOD + MOD) % MOD;
    for (int j = 1; j <= n; ++j) {
      write(X[i][j + n], " \n"[j == n]);
    }
  }
  return 0;
}