题目描述

解异或线性方程组

样例

blablabla

算法1

(高斯消元变式)

思路：系数矩阵转换为行阶梯形，由下往上逐渐消元.
(1)两个方程相互异或不影响解。(用于把当前列1消掉)
(2)任意一个数跟它本身^都为0(用来把系数消掉.)

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

const int N =110;
bool a[N][N];
int n,m ; 
int gauss()
{
    int c,r;//c列r行
    for(c = 0 ,r = 0;c < n ; c++)
    {
        int t = r;
        int len=N;
        for(int i = r;i< n ;i++)//(1)找到当列为1且所在的行.
        {

           if(a[i][c])t=i;
        }

        if(a[t][c]==false)continue;//判0;

        for(int i = c ;i<=n ;i++)swap(a[t][i],a[r][i]);//(2)将1出现的行换到最上面.


        for(int i = r+1;i<n;i++)//(4)把除当前行的所有第c列变为0;
        if(a[i][c])//不等于0;
            for(int j = n ; j>=c;j--)
            a[i][j]^=a[r][j];

        r++;
    }
    if(r<n)//存在系数为0的等式。
    {
        for(int i=r;i<n;i++)
        if(a[i][n]==true)//0=1
        return 2;//无解
        return 1;//有无穷多组解0=0
    }
    //由下往上消元过程.
    for(int i=n-1;i>=0;i--)
    {   

        for(int j=i+1;j<n;j++)
        {
                a[i][n] ^=a[i][j]*a[j][n];       
        }

    }
    return 0;//唯一解;
}
int main()
{
    cin>>n;
    for(int i = 0 ;i < n;i++)
        for(int j = 0;j<n+1;j++)
        cin>>a[i][j];

    int t = gauss();
    if(t==0)
    {
        for(int i= 0;i<n;i++)printf("%d\n",a[i][n]);
    }
    else if(t == 1)cout<<"Multiple sets of solutions"<<endl;
    else cout<<"No solution"<<endl;
    return 0;
}