高斯消元法解異或線性方程組

高斯消元法

對于一組線性方程組，枚舉每一列進行如下步驟：

1、找到首元非零行

2、将這一行交換到第一行

3、将這一行的第一個數變成1，對目前這一行進行操作，不涉及矩陣的初等變換

4、将下面所有行的目前列全部消成0，利用矩陣的初等變換

對于原異或方程組進行變換後

如果得到的矩陣是一個完美的上三角矩陣，則說明方程組有唯一解

否則會出現兩種情況：

1、推出沖突，即：零==非零，這種情況下表示無解

2、否則，即原異或方程組中有多餘的方程，此時有無窮多解

高斯消元解異或線性方程組

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
int n;
int a[N][N];
int gauss()
{
    int c, r; //c表示枚舉的哪一列，r表示枚舉的哪一行
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r; //記錄目前列
        for (int i = r; i < n; i++)
        {
            if (a[i][c])
                {t = i;break;}
        }
        if (!a[t][c]) continue;
        for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
        for (int i = r + 1; i < n; i++)
        {
            if (a[i][c])
            {
                for (int j = c; j <=n ; j++)
                    a[i][j] ^= a[r][j];
            }
        }
        r++;
    }
    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (a[i][n])
                return 2;
        return 1;
    }

    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;
}