无重载
#include <cstdio> #include <cstring> #define maxn 103 int n, k, mod; int ret[maxn][maxn], e[maxn][maxn]; void mult(int a[maxn][maxn], int b[maxn][maxn]) { int i, j, k; int c[maxn][maxn] = {0}; for(i = 0; i < 2*n; i++) for(j = 0; j < 2*n; j++) { for(k = 0; k < 2*n; k++) c[i][j] += a[i][k] * b[k][j], c[i][j] %= mod; } for(i = 0; i < 2*n; i++) for(j = 0; j < 2*n; j++) a[i][j] = c[i][j]; } void gao(int a[maxn][maxn], int b[maxn][maxn]) { int i, j, k; int c[maxn][maxn] = {0}; for(i = 0; i < n; i++) for(j = 0; j < n; j++) for(k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; for(i = 0; i < n; i++) for(j = 0; j < n; j++) a[i][j] = (c[i][j] + a[i][j+n]) % mod; } int a[maxn][maxn]; int main() { int i, j; scanf("%d%d%d", &n, &k, &mod); { for(i = 0; i < n; i++) for(j = 0; j < n; j++) { scanf("%d", &a[i][j]); if(a[i][j] >= mod) a[i][j] %= mod; } if(k == 1) { for(i = 0; i < n; i++, puts("")) for(j = 0; j < n;j ++) printf("%d ", a[i][j]); return 0; } k--; for(i = 0; i < n*2; i++) ret[i][i] = 1; for(i = 0; i < n; i++) for(j = 0; j < n; j++) e[i][j] = e[i][j+n] = a[i][j]; for(i = n; i < 2*n; i++) e[i][i] = 1; while(k) { if(k & 1) mult(ret, e); mult(e, e); k >>= 1; } gao(ret, a); for(i = 0; i < n; i++, puts("")) for(j = 0; j < n; j++) printf("%d ", ret[i][j]); } return 0; }
重载
#include <cstdio> #include <cstring> #define maxn 66 int n, k, mod; struct mat { int a[maxn][maxn]; mat() { memset(a, 0, sizeof(a)); } void print(){ printf("****************\n"); for(int i=0;i<n;i++) for(int j=0;j<n;j++) printf(j==n-1?"%d\n":"%d ",a[i][j]); printf("****************\n"); } friend mat& operator*(mat a, mat b) { mat c; int i, j, k; for(i = 0; i < 2*n; i++) for(j = 0; j < 2*n; j++) { for(k = 0; k < 2*n; k++) c.a[i][j] += a.a[i][k] * b.a[k][j], c.a[i][j] %= mod; } return c; } }; int a[maxn][maxn]; mat ret, e; int main() { scanf("%d%d%d", &n, &k, &mod); int i, j; for(i = 0; i < n; i++) { ret.a[i][i] = 1; for(j = 0; j < n; j++) scanf("%d", &a[i][j]), e.a[i][j+n] = e.a[i][j] = a[i][j], ret.a[i][i] = 1; } for(i = n; i < 2*n; i++) e.a[i][i] = ret.a[i][i] = 1; // ret.print(); // a.print(); while(k) { if(k & 1) ret = ret * e; e = e * e; k >>=1; } for(i = 0; i < n; i++, puts("")) for(j = n; j < 2*n; j++) printf("%d ", ret.a[i][j]); return 0; }