H - Problem H. Store The Matrix HDU - 6507 求矩阵的秩模板
题目链接：
H - Problem H. Store The Matrix
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：给你一个n*m的矩阵，然后这个矩阵可以分解成若干个矩阵相乘的结果，然后最终答案是所有的子矩阵的行和列相等累加，问你这个结果最小是多少。
具体思路：
然后就是矩阵的秩模板了：
int类型：
模板一
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 const int maxn = 2e5 + 100; 5 const int N = 50; 6 const int eps = 1e-6; 7 int a[N][N]; 8 int Rank(int n,int m) 9 { 10 int i=0,j=0,k,r,u; 11 while(i<n&&j<m) 12 { 13 r=i; 14 for(k=i; k<m; k++) 15 { 16 if(a[k][j]) 17 { 18 r=k; 19 break; 20 } 21 } 22 if(a[r][j]) 23 { 24 if(r!=i) 25 { 26 for(k=0; k<=n; k++) 27 { 28 swap(a[r][k],a[i][k]); 29 } 30 } 31 for(u=i+1; u<m; u++) 32 { 33 if(a[u][j]) 34 { 35 for(k=i; k<=n; k++) 36 { 37 a[u][k]^=a[i][k]; 38 } 39 } 40 } 41 ++i; 42 } 43 j++; 44 } 45 return i; 46 } 47 int main() 48 { 49 int n,m; 50 scanf("%d %d",&n,&m); 51 for(int i=1; i<=n; i++) 52 { 53 for(int j=1; j<=m; j++) 54 { 55 scanf("%d",&a[i][j]); 56 } 57 } 58 printf("%d\n",min(n*m,max(1,Rank(n,m))*(n+m)));/// 和1取最大是为了防止秩为0的时候，此时答案应为n*m 59 return 0; 60 }
View Code
模板二（高斯消元）
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 const int maxn = 2e5 + 100; 5 const int N = 50; 6 const int eps = 1e-6; 7 int a[N][N]; 8 int n,m; 9 void xchgline(int q,int w,int e) 10 { 11 int t; 12 for(int i=e; i<=m; i++) 13 { 14 swap(a[q][i],a[w][i]); 15 } 16 } 17 int Rank(int n,int m) 18 { 19 int s=0; 20 for(int i=1,j=1; i<=n&&j<=m; i++,j++) 21 { 22 int chk=0; 23 for(int v=i; v<=n; v++) 24 { 25 if(a[v][j]!=0) 26 { 27 chk=v; 28 break; 29 } 30 } 31 if(chk==0) 32 i--; 33 else 34 { 35 xchgline(chk,i,j); 36 for(int w=i+1; w<=n; w++) 37 { 38 if(a[w][j]!=0) 39 { 40 int g=__gcd(a[w][j],a[i][j]); 41 int pa=a[i][j]/g,pb=a[w][j]/g; 42 for(int z=j; z<=m; z++) 43 { 44 a[w][z]=a[w][z]*pa-a[i][z]*pb; 45 } 46 } 47 } 48 s++; 49 } 50 } 51 return s; 52 } 53 int main() 54 { 55 scanf("%d %d",&n,&m); 56 for(int i=1; i<=n; i++) 57 { 58 for(int j=1; j<=m; j++) 59 { 60 scanf("%d",&a[i][j]); 61 } 62 } 63 printf("%d\n",min(n*m,max(1,Rank(n,m))*(n+m)));/// 和1取最大是为了防止秩为0的时候，此时答案应为n*m 64 return 0; 65 }
View Code
更多精彩
