矩阵相关

ACM模版

矩阵乘法

/* * 矩阵乘法 n*n矩阵乘法 */ #define MAXN 111 #define mod(x) ((x) % MOD) #define MOD 1000000007 #define LL long long int n; struct mat { int m[MAXN][MAXN]; }; // 矩阵乘法 mat operator * (mat a, mat &b) { mat ret; memset(ret.m, 0, sizeof(ret.m)); for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if (a.m[i][k]) { for (int j = 0; j < n; j++) { ret.m[i][j] = mod(ret.m[i][j] + (LL)a.m[i][k] * b.m[k][j]); } } } } return ret; }

矩阵乘法 + 判等

/* * AB == C ??? */ struct Matrix { Type mat[MAXN][MAXN]; int n, m; Matrix() { n = m = MAXN; memset(mat, 0, sizeof(mat)); } Matrix(const Matrix &a) { set_size(a.n, a.m); memcpy(mat, a.mat, sizeof(a.mat)); } Matrix & operator = (const Matrix &a) { set_size(a.n, a.m); memcpy(mat, a.mat, sizeof(a.mat)); return *this; } void set_size(int row, int column) { n = row; m = column; } friend Matrix operator * (const Matrix &a, const Matrix &b) { Matrix ret; ret.set_size(a.n, b.m); for (int i = 0; i < a.n; ++i) { for (int k = 0; k < a.m; ++k) { if (a.mat[i][k]) { for (int j = 0; j < b.m; ++j) { if (b.mat[k][j]) { ret.mat[i][j] = ret.mat[i][j] + a.mat[i][k] * b.mat[k][j]; } } } } } return ret; } friend bool operator == (const Matrix &a, const Matrix &b) { if (a.n != b.n || a.m != b.m) { return false; } for (int i = 0; i < a.n; ++i) { for (int j = 0; j < a.m; ++j) { if (a.mat[i][j] != b.mat[i][j]) { return false; } } } return true; } };

矩阵快速幂

/* * 矩阵快速幂 n*n矩阵的x次幂 */ #define MAXN 111 #define mod(x) ((x) % MOD) #define MOD 1000000007 #define LL long long int n; struct mat { int m[MAXN][MAXN]; } unit; // 单元矩阵 // 矩阵乘法 mat operator * (mat a, mat &b) { mat ret; memset(ret.m, 0, sizeof(ret.m)); for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if (a.m[i][k]) { for (int j = 0; j < n; j++) { ret.m[i][j] = mod(ret.m[i][j] + (LL)a.m[i][k] * b.m[k][j]); } } } } return ret; } void init_unit() { for (int i = 0; i < MAXN; i++) { unit.m[i][i] = 1; } return ; } mat pow_mat(mat a, LL n) { mat ret = unit; while (n) { if (n & 1) { // n--; ret = ret * a; } n >>= 1; a = a * a; } return ret; } int main() { LL x; init_unit(); while (cin >> n >> x) { mat a; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a.m[i][j]; } } a = pow_mat(a, x); // a矩阵的x次幂 // 输出矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j + 1 == n) { cout << a.m[i][j] << endl; } else { cout << a.m[i][j] << " "; } } } } return 0; }

---

2017.6.13 修改矩阵乘法部分，优化，引用、判0