矩阵

1.基本运算(+, -, *)

struct Matrix { int n, m; LL map[MAXN][MAXN]; Matrix () { memset (map, 0, sizeof map); } void init () { for (int i = 0; i <= n; i++) map[i][i] = 1; } void cpy (LL a[][MAXN]) { for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { map[i][j] = a[i][j]; } } } void read () { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf ("%lld", &map[i][j]); map[i][j] %= MO; if (map[i][j] < 0) map[i][j] += MO; } } } void write () { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { printf ("%lld ", map[i][j]); } puts (""); } } Matrix operator * (const Matrix x) const { Matrix ans; ans.n = n; ans.m = x.m; for (int i = 1; i <= ans.n; i++) { for (int j = 1; j <= ans.m; j++) { for (int k = 1; k <= m; k++) { ans.map[i][j] += map[i][k] * x.map[k][j]; ans.map[i][j] %= MO; if (ans.map[i][j] < 0) ans.map[i][j] += MO; } } } return ans; } Matrix operator + (const Matrix x) const { Matrix ans; ans.n = n; ans.m = m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ans.map[i][j] = map[i][j] + x.map[i][j]; } } return ans; } Matrix operator - (const Matrix x) const { Matrix ans; ans.n = n; ans.m = m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ans.map[i][j] = map[i][j] + x.map[i][j]; } } return ans; } };

2.压行

struct Matrix {int n, m;LL map[Maxn][Maxn];Matrix () { memset (map, 0, sizeof map); }void init () {for (int i = 0; i <= n; i++)map[i][i] = 1;}void cpy (LL a[][Maxn]) {for (int i = 0; i < Maxn; i++) {for (int j = 0; j < Maxn; j++) {map[i][j] = a[i][j];}}}void read () {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf ("%lld", &map[i][j]);map[i][j] %= mod;if (map[i][j] < 0) map[i][j] += mod;}}}void write () {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {printf ("%lld ", map[i][j]);}puts ("");}}Matrix operator * (const Matrix x) const {Matrix ans; ans.n = n; ans.m = x.m;for (int i = 1; i <= ans.n; i++) {for (int j = 1; j <= ans.m; j++) {for (int k = 1; k <= m; k++) {ans.map[i][j] += map[i][k] * x.map[k][j];ans.map[i][j] %= mod;if (ans.map[i][j] < 0) ans.map[i][j] += mod; }}}return ans;}Matrix operator + (const Matrix x) const {Matrix ans; ans.n = n; ans.m = m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ans.map[i][j] = map[i][j] + x.map[i][j];}}return ans;}Matrix operator - (const Matrix x) const {Matrix ans; ans.n = n; ans.m = m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ans.map[i][j] = map[i][j] + x.map[i][j];}}return ans;}};