第一道高斯消元题目~
题目：有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）0<=N<=29
我们用样例来模拟一下：
我的高斯消元求解异或方程组模版：
int gauss()
{
int i,j,k,l;
//j=当前要消第几个元
//i=当前消了几个元+1(n-i+1就是*元个数),也就是当前j要处理的这个方程将要放在第i行，构成上三角矩阵。
//i、j不等是因为有些元是*元，不需要消,这些方程放到最后面（维护上三角矩阵）。
for(i=,j=;i<=n && j<=n;j++)
{
for(k=j;k<=n;k++)
if(a[k][j]) break;//先找到一个这个元的系数不为0方程的换到第i行。
if(a[k][j])
{
for(l=;l<=n+;l++) swap(a[i][l],a[k][l]);
for(l=;l<=n;l++)//注意这里从1开始，因为把最后回代的过程合并了
{
if(l!=i && a[l][j])//如果系数不为0才异或消元
for(k=;k<=n+;k++)
a[l][k]^=a[i][k];
}
i++;
}
}
for(j=i;j<=n;j++)
if(a[j][n+]) return -;
return <<(n-i+);
}
说一下解的个数问题：
对增广矩阵[A b]做初等行变换，化成阶梯形（高斯消元法），如果存在[0,0,…,0,1]的行，就是无解；如果存在r行[0,0,…,0,0]，就意味着有r个*变量，因为这里的变量只取0/1，所以有2r个解；如果不存在[0,0,…,0,*]，即把最后一行去掉后不存在全0行，则A为满秩矩阵，则方程组有唯一解。
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std; const int N=;
int n,bit[N],a[N][N]; void output()
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n+;j++)
printf("%d ",a[i][j]);
printf("\n");
}
printf("\n");
} int gauss()
{
int i,j,k,l;
//j=当前要消第几个元
//i=当前消了几个元+1(n-i+1就是*元个数),也就是当前j要处理的这个方程将要放在第i行，构成上三角矩阵。
//i、j不等是因为有些元是*元，不需要消,这些方程放到最后面（维护上三角矩阵）。
for(i=,j=;i<=n && j<=n;j++)
{
for(k=j;k<=n;k++)
if(a[k][j]) break;//先找到一个这个元的系数不为0方程的换到第i行。
if(a[k][j])
{
for(l=;l<=n+;l++) swap(a[i][l],a[k][l]);
for(l=;l<=n;l++)//注意这里从1开始，因为把最后回代的过程合并了
{
if(l!=i && a[l][j])//如果系数不为0才异或消元
for(k=;k<=n+;k++)
a[l][k]^=a[i][k];
}
i++;
}
}
for(j=i;j<=n;j++)
if(a[j][n+]) return -;
return <<(n-i+);
} int main()
{
int T,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(a,,sizeof(a));
for(int i=;i<=n;i++) scanf("%d",&a[i][n+]);
for(int i=;i<=n;i++)
{
scanf("%d",&x);
a[i][n+]^=x;
}
while()
{
scanf("%d%d",&x,&y);
if(!x && !y) break;
a[y][x]=;
}
for(int i=;i<=n;i++) a[i][i]=;
int ans=gauss();
if(ans==-) printf("Oh,it's impossible~!!\n");
else printf("%d\n",ans);
}
return ;
}