题目描述
Given a matrix M with r rows and c columns. It is obviously that we need r × c elements to store this matrix.
However, for a specifi matrix M , we may be able to represent M as “Matrix-chain multiplication” likes M = A1 ×A2···×An, where n ≥ 1 and each Ai is a matrix with size ri ×ci. Then we can use (***)elements to store {A1, A2 . . . , An} instead of storing M directly.
We want to know: if we represent M in the optimal way, how many elements are needed at least to store M ?
However, for a specifi matrix M , we may be able to represent M as “Matrix-chain multiplication” likes M = A1 ×A2···×An, where n ≥ 1 and each Ai is a matrix with size ri ×ci. Then we can use (***)elements to store {A1, A2 . . . , An} instead of storing M directly.
We want to know: if we represent M in the optimal way, how many elements are needed at least to store M ?
输入
Input is given from Standard Input in the following format:
r c
M1,1 M1,2 . . . M1,c
M2,1 M2,2 . . . M2,c
...
Mr,1 Mr,2 . . . Mr,c
Constraints
1 ≤ r, c ≤ 30
0 ≤ Mi,j ≤ 1000(1 ≤ i ≤ r, 1 ≤ j ≤ c) (Note that although all Mi,j are non-negative integers in the input, we think the element type is float number with infinity precision and can be negative) .
r c
M1,1 M1,2 . . . M1,c
M2,1 M2,2 . . . M2,c
...
Mr,1 Mr,2 . . . Mr,c
Constraints
1 ≤ r, c ≤ 30
0 ≤ Mi,j ≤ 1000(1 ≤ i ≤ r, 1 ≤ j ≤ c) (Note that although all Mi,j are non-negative integers in the input, we think the element type is float number with infinity precision and can be negative) .
输出
Print one integer denotes the minimal number of elements needed.
样例输入
3 3
1 0 1
0 0 0
1 0 1
样例输出
6
提示
大胆假设，不会证明。假设矩阵的秩为s，则一个矩阵可表示为一个r*s的矩阵乘以一个s*c的矩阵，第一个矩阵再向下分解只会让元素变多，第二个矩阵为满秩矩阵。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 110; int n, m, a[N][N], b[N][N], P; int Pow(int x, int t) { int r = 1; for (; t; t >>= 1, x = ll(x) * x % P) if (t & 1)r = ll(r) * x % P; return r; } int inv(int x) { return Pow(x, P - 2); } void pp(int &x, int d) { if ((x += d) >= P)x -= P; } int Rank() { P = 1e9 + 7; int rk = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[i][j] = a[i][j]; for (int i = 0, j = 0; i < n && j < m; ++i, ++j) { int c = -1; for (int k = i; k < n; k++) if (b[k][j]) { c = k; break; } if (c == -1) --i; else { ++rk; for (int k = j; k < m; k++) swap(b[i][k], b[c][k]); int cof = inv(b[i][j]); for (int k = j; k < m; k++) b[i][k] = ll(b[i][k]) * cof % P; for (int x = i + 1; x < n; x++) if (b[x][j]) for (int y = m - 1; y >= j; y--) pp(b[x][y], P - ll(b[x][j]) * b[i][y] % P); } } return rk; } int main() { //freopen("input.txt", "r", stdin); cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j]; int ra = max(1, Rank()); cout << min(n * m, (n + m) * ra) << endl; return 0; }