记录编号	600756	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	4.882 s
提交时间	2025-05-14 19:20:52	内存使用	4.67 MiB

#include <bits/stdc++.h>
#define ll __int128
#define Tairitsu fast_pow
#define Tempest return 0;
using namespace std;
ll n, k, mod;
ll read() {
	ll sum = 0, fl = 1;
	int ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}
void write(ll x) {
	static ll sta[40];
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);
	putchar(' ');
}
struct Matrix {
	ll a[40][40];
	void Clear() {
		memset(a, 0, sizeof a);
	}
	void Print() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				write(a[i][j]);
			}
			printf("\n");
		}
	}
	Matrix operator * (Matrix y) {
		Matrix res;
		res.Clear();
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				for (int k = 1; k <= n; ++k) {
					res.a[i][j] += a[i][k] % mod * y.a[k][j] % mod;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	Matrix operator + (Matrix y) {
		Matrix res;
		res.Clear();
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				res.a[i][j] = a[i][j] % mod + y.a[i][j] % mod;
				res.a[i][j] %= mod;
			}
		}
		return res;
	}
	Matrix operator - (Matrix y) {
		Matrix res;
		res.Clear();
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				res.a[i][j] = a[i][j] - y.a[i][j];
				res.a[i][j] = ((res.a[i][j] % mod) + mod) % mod;
			}
		}
		return res;
	}
};
struct Matrix2 {
	Matrix a[3][3];
	void Clear() {
		for (int i = 1; i <= 2; ++i) {
			for (int j = 1; j <= 2; ++j) {
				a[i][j].Clear();
			}
		}
	}
	Matrix2 operator * (Matrix2 y) {
		Matrix2 res;
		res.Clear();
		for (int i = 1; i <= 2; ++i) {
			for (int j = 1; j <= 2; ++j) {
				for (int k = 1; k <= 2; ++k) {
					res.a[i][j] = res.a[i][j] + (a[i][k] * y.a[k][j]);
				}
			}
		}
		return res;
	}
};
Matrix2 Tairitsu(Matrix2 x, ll y) {
	Matrix2 res = x;
	y--;
	while (y) {
		if (y & 1) res = res * x;
		y >>= 1;
		x = x * x;
	}
	return res;
}
Matrix A, E, O;
Matrix2 M;
Matrix X;

int main() {
	n = read(), k = read(), mod = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			A.a[i][j] = read();
			A.a[i][j] %= mod;
		}
		E.a[i][i] = 1;
	}
	M.a[1][1] = A, M.a[1][2] = E, M.a[2][1] = O, M.a[2][2] = E;
	(Tairitsu(M, k + 1).a[1][2] - E).Print();
	Tempest
}