跳转至

高斯消元相关

求解异或方程组

传参 \(n\) 是方程个数，\(m\) 是未知元个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
namespace Gauss_Xor
{
    bitset<MAX> mat[MAX];
    inline void Gauss(int n,int m)
    {
        int x=0,y=0;
        for(;y<m;++y)
        {
            int now=x;
            while(now<n&&!mat[now][y]) ++now;
            if(now==n) continue;
            swap(mat[x],mat[now]);
            for(int i=0;i<n;++i) if(i!=x&&mat[i][y]) mat[i]^=mat[x];
            ++x;
        }
    }
}

求解行列式

使用辗转相除法，搭配 ModNum 使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
namespace Determinant
{
    vector<vector<int>> A;

    inline int SolveDet()
    {
        int det=1,N=A.size()-1;
        for(int i=0;i<N;++i) for(int j=i+1;j<N;++j) while(A[j][i])
        {
            int tmp=A[i][i]/A[j][i];
            for(int k=i;k<N&&tmp;++k) Mdel(A[i][k],Cmul(A[j][k],tmp));
            swap(A[i],A[j]),det=-det;
        }
        Mmod(det);
        for(int i=0;i<N;++i) if(A[i][i]) Mmul(det,A[i][i]);
        return det;
    }
}