题解 P2447 【[SDOI2010]外星千足虫】
leozhang
·
·
题解
高斯消元解异或方程组裸题
首先介绍一下异或方程组：异或方程组是形如x_1^x_2^...^x_n=1(或0)(x_i\in{0,1})的一组方程，我们的目的是求出x_i的值
乍一看，这好像并不好做，最暴力的方法是O(2^n)枚举
但是有了高斯消元，我们就可以不这么暴力了，而是可以借助高斯消元的思想来解了
举个例子：
现在我们有一个方程组长这样：
x_1$^$x_3$=$0
x_1$^$x_2$=$0
x_1$^$x_2$^$x_3$=$1
（当然，给出的例子是很简单的了）
但是我们可以借助这种思想：我们首先观察第一个方程：我们希望只有这一个方程中含有x_1（这也是高斯消元的思想），这样在其他变量已知的情况下我们就可以求出x_1了
那么根据异或的性质，我们用第一个方程逐个与下面含有x_1的方程异或，就可以消去下面所有的x_1！
于是做出来的结果就长这样：
x_1$^$x_3$=$0
x_2$^$x_3$=$0
x_2$=$1
接下来就是第二个方程：我们要把下面的x_2消掉，于是我们的方法同上
最后结果长这样：
x_1$^$x_3$=$0
x_2$^$x_3$=$0
x_3$=$1
最后一个方程，发现已经结束了，那么到这里结束，我们向上回代即可
而回代的原理，也很简单：
所以我们算出$x_3$后将所有有$x_3$的等式两侧异或$x_3$即可，于是方程就变成了这样：
$x_1$=$1
x_2$=$1
x_3$=$1
是不已经解出来了？
这就是高斯消元解异或方程组的过程及原理
但是这里会出现一个问题：“自由元”问题
按道理，给出n个方程组应该是可以解出每个答案的，但是由于异或运算特殊的性质，有时n个方程是难以解出每个值的
为什么？
举个例子：
$x_2$^$x_3$=1
$x_1$^$x_3$=0
不难发现，这组方程本身解就不唯一（显然，$(1,0,1)$与$(0,1,0)$都是该方程组的解）
（如果去探索本质的原因：上面的异或方程在逻辑上等同于以下两个方程：$x_1==x_3$且$x_1!=x_2$，那么考虑取值的方式，不难发现解不是唯一的）
那么如果用正常的方式来解，最后会变成这种形式：
$x_1$^$x_2$=1
$x_2$^$x_3$=1
这也能看出来，因为丢失了一个方程啊！
这时我们就称$x_3$是一个自由元，也就是他的值既可以为0又可以为1，此时该异或方程组有很多组解！
对于自由元问题，目前仅有的办法就是dfs，枚举每个自由元的状态然后回代求解
但是对于这道题，我们没有必要这么做
由于对于解不唯一的情况，他只要求输出一句话，所以我们只需在解不唯一的情况下（也就是解了全部方程仍不能得到唯一解时）特判即可
接下来我们就可以研究如何输出最小方程数了
首先有个显而易见的事情：至少需要n个方程才能解出所有未知数
那我们就先拿出n个方程去解，看看是否存在自由元，如果存在的话就再加入一个，直到解出唯一解或用完所有方程为止
要记录所有自由元的位置
然后就结束了
```cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n,m;
int a[2005][1005];
char ch[2005];
bool vis[2005];
int Gauss()
{
int ret=0;
for(int i=1;i<=n;i++)
{
int temp=i;
while(!a[temp][i]&&temp<=n)temp++;
if(temp==n+1){ret++;continue;}
vis[i]=1;
if(i!=temp)for(int j=i;j<=n+1;j++)swap(a[temp][j],a[i][j]);
for(int j=i+1;j<=n;j++)
{
if(!vis[j]&&a[j][i])for(int k=i;k<=n+1;k++)a[j][k]^=a[i][k];
}
}
return ret;
}
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
scanf("%s",ch+1);
a[i][n+1]=read();
for(int j=1;j<=n;j++)a[i][j]=ch[j]-'0';
}
int now=n;
while(Gauss())
{
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
now++;
if(now>m)
{
printf("Cannot Determine\n");
return 0;
}
swap(a[now],a[i]);
}
}
}
for(int i=n;i>=1;i--)for(int j=i-1;j>=1;j--)if(a[j][i])a[j][n+1]^=a[i][n+1];
printf("%d\n",now);
for(int i=1;i<=n;i++)
{
if(a[i][n+1])printf("?y7M#\n");
else printf("Earth\n");
}
return 0;
}
```