【算法】高斯消元

【题解】

高斯消元经典题型：异或方程组

异或相当于相加后mod2

异或方程组就是把加减消元全部改为异或。

异或性质：00 11为假，01 10为真。与1异或取反，与0异或不变。

建图：对于图上每个点x列一条异或方程，未知数为n个灯按不按，系数为灯i按了点x变不变，该行结果n+1为初始状态。（所以a[x][y]其实表示x和y是否存在异或关系）

建图原理见上面链接。

寻找：因题目保证有解，而系数只有0或1，所以不用找最大，找到一个非0系数即可。

消元：只针对对应变量系数为1的，全部异或即可。

回代：因为每行的主元素i系数必为1，所以该行结果一定与该行主元素相同(1*x=x)

因此只要把i+1~n的系数为1的结果与该行结果异或即可。

注意打印编号的时候要从0累加，而不是用累减的数据组数……

#include
      
       #include
       
        #include
        
         using namespace std;const int n=30;int tt,a[n+10][n+10];void gauss()//保证有解 {    int r;    for(int i=1;i<=n;i++)     {         for(int j=i;j<=n;j++)if(a[j][i]){r=j;break;}         if(r!=i)for(int j=1;j<=n+1;j++)swap(a[i][j],a[r][j]);         for(int j=i+1;j<=n;j++)if(a[j][i])          for(int k=i;k<=n+1;k++)           a[j][k]^=a[i][k];     }    for(int i=n;i>=1;i--)     for(int j=i+1;j<=n;j++)      if(a[i][j])a[i][n+1]^=a[j][n+1];}int main(){    scanf("%d",&tt);    int t=0;    while(tt--)     {         t++;         memset(a,0,sizeof(a));         for(int i=1;i<=n;i++)         {             scanf("%d",&a[i][n+1]);             a[i][i]=1;             if(i%6!=1)a[i][i-1]=1;             if(i%6!=0)a[i][i+1]=1;             if(i>6)a[i][i-6]=1;             if(i<25)a[i][i+6]=1;         }        gauss();        printf("PUZZLE #%d\n",t);        for(int i=1;i<=n;i++)         {             if(!(i%6))printf("%d\n",a[i][n+1]);             else printf("%d ",a[i][n+1]);         }     }    return 0;}