【算法】高斯消元
【题解】
高斯消元经典题型：异或方程组
异或相当于相加后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<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=;
int tt,a[n+][n+];
void gauss()//保证有解
{
int r;
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)if(a[j][i]){r=j;break;}
if(r!=i)for(int j=;j<=n+;j++)swap(a[i][j],a[r][j]);
for(int j=i+;j<=n;j++)if(a[j][i])
for(int k=i;k<=n+;k++)
a[j][k]^=a[i][k];
}
for(int i=n;i>=;i--)
for(int j=i+;j<=n;j++)
if(a[i][j])a[i][n+]^=a[j][n+];
}
int main()
{
scanf("%d",&tt);
int t=;
while(tt--)
{
t++;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i][n+]);
a[i][i]=;
if(i%!=)a[i][i-]=;
if(i%!=)a[i][i+]=;
if(i>)a[i][i-]=;
if(i<)a[i][i+]=;
}
gauss();
printf("PUZZLE #%d\n",t);
for(int i=;i<=n;i++)
{
if(!(i%))printf("%d\n",a[i][n+]);
else printf("%d ",a[i][n+]);
}
}
return ;
}