柒葉灬 的博客

柒葉灬 的博客

高斯消元总结(个人笔记)

posted on 2018-12-23 22:00:37 | under 专题总结 |

高斯消元


高斯消元的复杂度: $O(n^3)$

给定 $n$ 未知数和 $m$ 个 $n$ 元 $1$ 次方程 ,在 $O(n^3)$ 的时间内求出解。

例如:

$$\begin{cases}a_{11}x_1+a_{12}x_2+a_{13}x_3=y_1\\a_{21}x_1+a_{22}x_2+a_{23}x_3=y_2\\a_{31}x_1+a_{32}x_2+a_{33}x_3=y_3\end{cases}$$


模板:

int Gauss(){
    int col=1,k=1;//col表示第几个未知数,k表示第几个方程
    for(;col<=n && k<=m;col++,k++){
        int r=k;
        for(int i=k+1;i<=m;i++)
            if(fabs(a[i][col])>fabs(a[r][col]))r=i;
        if(r!=k){
            for(int i=col;i<=n+1;i++)
                swap(a[r][i],a[k][i]);
        }
        if(fabs(a[k][col])<eps){
            k--;
            continue;
        }
        for(int i=k+1;i<=m;i++){
            if(fabs(a[i][col])<eps)continue;
            double p=a[i][col]/a[k][col];
            for(int j=col;j<=n+1;j++)
                a[i][j]-=a[k][j]*p;
        }
    }
    for(int i=k;i<=m;i++)
        if(fabs(a[i][n+1])>eps)return -1;
    //方程左边为0  但方程右边不是0  所以无解

    if(k<=n)return n-k+1;
    //返回自由元的个数,注意是用了k-1个方程

    for(int i=n;i>=1;i--){
        double tmp=a[i][n+1];
        for(int j=i+1;j<=n;j++)
            tmp-=a[i][j]*x[j];
        x[i]=tmp/a[i][i];
    }
    return 0;
    //表示有解
}

高斯消元——异或方程组

本质上和上面的方程组没什么区别,就是稍微改一下就可以了。

形如:

$$\begin{cases}(a_{11}*x_1) \bigoplus (a_{12}*x_2) \bigoplus (a_{13}*x_3)=y_1\\(a_{21}*x_1) \bigoplus (a_{22}*x_2) \bigoplus (a_{23}*x_3)=y_2\\(a_{31}*x_1) \bigoplus (a_{32}*x_2) \bigoplus (a_{33}*x_3)=y_3\end{cases}$$

需要注意的是,系数 $a$ , 未知数 $x$ , 结果 $y$ 必须都是 $0$ 或者 $1$ .


模板:

int Gauss(){
    int col=1,k=1;
    for(;col<=n && k<=m;col++,k++){
        int r;
        for(int i=k;i<=m;i++)
            if(a[i][col]==1){
                r=i;
                break;
            }
        if(r!=k){
            for(int i=col;i<=n+1;i++)
                swap(a[k][i],a[r][i]);
        }
        if(a[k][col]==0){
            k--;
            continue;
        }
        for(int i=k+1;i<=m;i++){
            if(a[i][col]==0)continue;
            for(int j=col;j<=n+1;j++)
                a[i][j]^=a[k][j];
        }
    }
    for(int i=k;i<=m;i++)
        if(a[i][n+1]!=0)return -1;
    if(k<=n)return n-k+1;

    for(int i=k-1;i>=1;i--){
        int p=a[i][n+1];
        for(int j=i+1;j<=n;j++)
            p^=a[i][j]*x[j];
        x[i]=p;
    }
    return 0;

顺便写一道题解:HDU3915

题目大意:给 $n$ 个数字,去掉其中的一些数字(也可以不去),使得剩下的数异或和为0,问总的方案数?

我们可以列出一条方程:

$$ (a_1*A_1) \bigoplus (a_2*A_2) \bigoplus ... \bigoplus (a_n*An)=0$$

但显然这样是不行的,因为 $A_i$ 不一定是 $0$ 或 $1$ 。所以需要拆分,考虑拆成 $31$ 位,这样我们就能得到 $31$ 条方程,满足了异或方程解出来的条件(未知数只能是 $01$ )。

接下来考虑答案,显然如果方程有唯一解的话,那么 $ans=1$ ,

如果不是唯一解,说明就有多个自由元,

如果自由元的个数是 $K$ 个的话,那么 $ans=2^K$


补充一下自由元与主元的关系:

$$\begin{cases} x_1=a_1x_3+a_2x_4+a_3x_5\\x_2=b_1x_3+b_2x_4+b_3x_5 \end{cases}$$

如果自由元每一个都确定了,那么主元也就全部确定了,因为自由元的方案数总共是 $2^K$ ,所以所有解的个数也就是 $2^K$