求矩阵的秩,及判断有无解
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<utility> using namespace std; typedef long long LL; const int N = 60, INF = 0x3F3F3F3F; const double eps = 1e-8; template<typename T> int gauss_jordan(T A[N][N], int n, int m){ int i, c; for(i = 0, c = 0; i < n && c < m; i++, c++){ int r = i; for(int j = i + 1; j < n; j++){ if(A[j][c]){ r = j; break; } } if(A[r][c] == 0){ i--; continue; } if(r != i){ for(int j = 0; j <= m; j++){ swap(A[r][j], A[i][j]); } } for(int k = 0; k < n; k++){ if(k != i && A[k][c]){ for(int j = m; j >= c; j--){ A[k][j] ^= A[i][j]; } } } } for(int j = i ; j < n; j++){ if(A[j][m]){ return -1; } } return i; } int a[N][N], b[N][N]; int main(){ int t; cin>>t; for(int cas = 1; cas <= t; cas++){ int n, m; scanf("%d %d", &n, &m); memset(b, 0, sizeof(b)); for(int i = 0; i < m; i++){ int cnt; scanf("%d", &cnt); while(cnt--){ int v; scanf("%d", &v); v--; b[v][i] = 1; } } int q; scanf("%d", &q); printf("Case %d:\n", cas); while(q--){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ a[i][j] = b[i][j]; } } for(int i = 0; i < n; i++){ scanf("%d", &a[i][m]); } int ans = gauss_jordan(a, n, m); if(ans == -1){ printf("0\n"); }else{ printf("%I64d\n", 1ll << (m - ans)); } } } return 0; }