UVA11542 Square(高斯消元异或方程组)-白红宇

UVA11542 Square(高斯消元异或方程组)

阅读量：6257 次

发布时间：2019-06-22

本文共 3195 字，大约阅读时间需要 10 分钟。

建立方程组消元，结果为2 ^(自由变元的个数) - 1

采用高斯消元求矩阵的秩

方法一：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long LL;const int N = 108, INF = 0x3F3F3F3F;const double eps = 1e-8;int a[N][N];template
                
                 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]; } } } } return i;}const int MAXN = 508;int prime[MAXN];bool vis[MAXN];int getPrime(int n){//求1~n的素数 int tot=0; memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++){ if(!vis[i]){ prime[tot++]=i; } for(int j=0;j
                 
                  <=n;j++){ vis[i*prime[j]]=true; if(i%prime[j]==0){//让每个合数仅被其最小的质数筛去 break; } } } return tot;}int main(){ int cnt = getPrime(500); int t; cin>>t; while(t--){ memset(a, 0, sizeof(a)); int n; cin>>n; for(int j = 0; j < n; j++){ LL x; cin>>x; for(int i = 0; i < cnt && prime[i]<= x; i++){ while(x % prime[i] == 0){ a[i][j] ^= 1; x /= prime[i]; } } } LL ans = n - gauss_jordan(a, cnt, n); //cout<
                  
                   <<" ans\n"; cout<<((1ll << ans) - 1)<<'\n'; } return 0;}

方法2：

消元后非0向量的行数即为矩阵的秩，但开始出现问题一直WA，后来在消元变成上三角矩阵后，从最后一行起，找出第一个非0元素，向上消元。

应该有更巧妙的写法避免这个问题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long LL;const int N = 108, INF = 0x3F3F3F3F;const double eps = 1e-8;int a[N][N];template
                
                 void gauss_jordan(T A[N][N], int n, int m){ for(int i = 0; i < n; i++){ int r = i; for(int j = i + 1; j < n; j++){ if(A[j][i]){ r = j; break; } } if(A[r][i] == 0){ continue; } if(r != i){ for(int j = 0; j <= m; j++){ swap(A[r][j], A[i][j]); } } for(int k = i + 1; k < n; k++){ if(k != i && A[k][i]){ for(int j = m; j >= i; j--){ A[k][j] ^= A[i][j]; } } } } for(int i = n - 1; i > 0; i--){ for(int j = 0; j < m; j++){ if(A[i][j]){ for(int k = i - 1; k >= 0; k--){ if(A[k][j]){ for(int l = j; l <= m; l++){ A[k][l] ^= A[i][l]; } } } break; } } }}const int MAXN = 508;int prime[MAXN];bool vis[MAXN];int getPrime(int n){//求1~n的素数 int tot=0; memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++){ if(!vis[i]){ prime[tot++]=i; } for(int j=0;j
                 
                  <=n;j++){ vis[i*prime[j]]=true; if(i%prime[j]==0){//让每个合数仅被其最小的质数筛去 break; } } } return tot;}int main(){ int cnt = getPrime(500); int t; cin>>t; while(t--){ memset(a, 0, sizeof(a)); int n; int row = 0; cin>>n; for(int j = 0; j < n; j++){ LL x; cin>>x; for(int i = 0; i < cnt && prime[i]<= x; i++){ while(x % prime[i] == 0){ row = max(row, i); a[i][j] ^= 1; x /= prime[i]; } } } row++; gauss_jordan(a, row, n); int rk = 0; for(int i = 0; i < row; i++){ for(int j = 0; j < n; j++){ if(a[i][j]){ rk++; break; } } } n -= rk; cout<<((1ll << n) - 1)<<'\n'; } return 0;}