2.3 高斯消元法求解异或方程组

异或（eXclusive OR, XOR）是一个逻辑运算符，异或的数学符号为“⊕”，运算法则为0⊕0=0、1⊕0=1、0⊕1=1、1⊕1=0，即同为0、异为1。

按位异或是指参与运算的两个值，如果两个相应的二进制位相同，则结果为0，否则结果为1。C、C++、Java的按位异或运算符为“^”，例如，10100001^00000110=10100111。

异或方程组是形如的方程组，其中，aij、xi和bi取值为0或1，其中1≤i,j≤n。

高斯消元法求解异或方程组的方法如下。异或方程组对应的增广矩阵用二维数组a表示。对于k=1,…,n，找到a[i][k]不为0的行i，将该行与第k行交换；然后，用第k行去异或第k行下面所有a[i][j]不为0的行i，消去它们的第k个系数，这样就将原来的增广矩阵转换成上三角矩阵。

由于最后一行只有一个变量，求出这个变量，然后用它跟上面所有含有该变量的方程异或，以此类推即可自下而上求出所有变量。

下面给出高斯消元法求解异或方程组的程序模板。

题目2.3.1、题目2.3.2和题目2.3.3是应用高斯消元法求异或方程组的范例。

【2.3.1 开关问题】

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关时，其他与此开关相关联的开关也会相应地发生变化，即这些互相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是计算有多少种可以达到指定状态的方法。（不计开关操作的顺序。）

输入

输入的第一行有一个数K，表示以下有K组测试数据。

每组测试数据的格式如下。

●第一行，一个数N(0<N<29)。

●第二行，N个为0或者1的数，表示开始时N个开关的状态。

●第三行，N个为0或者1的数，表示操作结束后N个开关的状态。

接下来，每行两个数I、J，表示如果操作第I个开关，第J个开关的状态也会变化。每组数据以“00”结束。

输出

如果有可行方法，输出总数，否则输出“Oh, it’s impossible～!!”（不包括引号）。

提示

对于第一组数据，共有以下四种操作方法：操作开关1；操作开关2；操作开关3；操作开关1、2、3（不记顺序）。

试题来源：LIANGLIANG@POJ

在线测试：POJ 1830

试题解析

本题要求计算开关从初始状态变到目标状态有多少种变换方式。

设n×n方阵A表示n个开关的关联关系，方阵A的列向量Ai表示变换第i个开关会影响到哪些开关，A[j][i]=1表示变换第i个开关的操作能够影响第j个开关的状态，而A[j][i]=0则表示变换第i个开关的操作不会影响第j个开关的状态；显然，A[i][i]=1。列向量X表示开关的操作，X[i]取值为1或者0，分别表示第i个开关变换或者不变换。列向量B表示初始状态和目标状态异或运算的结果。

所以，如果A[j][i]=1，且X[i]=1，则A[j][i]×X[i]=1，表示第i个开关的状态改变；如果A[j][i]=0，则A[j][i]×X[i]=0，表示第i个开关的状态不变；如果X[i]==0，表示不对第i个开关操作，则对第j个开关的状态也没有影响，即A[j][i]×X[i]=0，此时第i个开关状态不变。则A[j][1]×X[1]⊕A[j][2]×X[2]⊕…⊕A[j][n]×X[n]=B[j]，1≤j≤n。

本题求解用异或方程组AX=B表示，然后进行高斯消元求解。

当化简后增广矩阵的秩等于原矩阵的秩且等于n时，即化简后为绝对的上三角矩阵，X有唯一解；当化简后增广矩阵的秩等于原矩阵的秩且小于n时，有多组解；设自由变量有y个，可行方法的总数为2y；当化简后增广矩阵的秩与原矩阵的秩不相等时，即增广矩阵化简后存在（0, 0, 0,…, a）的情况，则无解。

例如，对于样例输入的第一组数据，方阵A是全1阵，矩阵运算表示为=，即相应的异或方程组为，则增广矩阵为；所以，自由变量有2个，可行方法的总数为22=4。

对于样例输入的第二组数据，矩阵运算表示为，则相应的异或方程组为，则增广矩阵为，由矩阵第2行可知，得无解。

参考程序

【2.3.2 Extended Lights Out】

游戏Lights Out的扩展版本是一个5行、每行6个按钮的智力游戏面板（实际上，游戏是5行，每行5个按钮），每个按钮也都是灯。当一个按钮被按下时，该按钮及其上、下、左、右（最多四个）相邻按钮的灯的状态都会反转，即：如果原来灯开着，就关灯；如果灯关着，就开灯。如果按下面板角落上的按钮，则改变相应的3个按钮的状态；如果按下边上的按钮，则改变相应的4个按钮的状态；按下其他按钮，则改变相应的5个按钮的状态。例如，在图2.3-1中，如果按下左侧游戏面板中标有×的按钮，则游戏面板变为右侧的面板。

这个游戏从面板上一组初始的灯的状态开始，通过按下按钮，使面板上所有的灯都关上。当按下相邻的按钮时，一次按钮可以抵消另一次按钮所产生的效果。例如，在图2.3-2所示的实例中，按左侧面板上标记×的按钮，将产生右侧的面板状态。这里要注意，第2行第3列和第2行第5列的按钮都改变了第2行第4列的按钮的状态，因此，最终该按钮的状态不变。

这里要注意以下几点。

●按下按钮的顺序无关紧要。

●如果一个按钮被第二次按下，将完全抵消第一次按下该按钮的效果，因此任何按钮都不需要被多次按下。

●如图2.3-2所示，通过按下第2行中的相应按钮，可以关上第一行中的所有灯。通过在每一行重复这一过程，前4行中的所有灯都能关上。同样，按第2, 3,…列中的按钮，前5列中的所有灯都可以被关上。

请编写一个程序解这个游戏。

输入

输入的第一行是一个正整数n，给出后面的游戏面板数。每个面板是5行，每行有6个由一个或多个空格隔开的0或1，其中，0表示灯已关，1表示灯开着。

输出

对于每个游戏面板，首先，输出一行字符串“PUZZLE #m”，其中m是输入中游戏面板的序号。在这一行之后是一个类似游戏面板的展示（与输入的格式相同），在展示中，1表示要解该游戏，必须按下这一位置的按钮，而0表示不要按下相应的按钮。在输出的面板显示中，每个0或1之间要正好有一个空格。

试题来源：ACM Greater New York 2002

在线测试：POJ 1222，UVA 2561

试题解析

本题给出一个5×6的矩阵，矩阵中的每个值都表示相应位置的按钮灯的状态，1表示灯亮，0表示灯灭。每当按下一个位置的按钮，它和它相邻的灯的状态全部翻转。在这样的矩阵中，按下哪些按钮可以把整个矩阵都变成灯灭，1表示按了，0表示没按。其中，按按钮的顺序可以是任意的，而且，任何一个按钮都最多只需要按下一次，因为按下第二次刚好抵消第一次，等于没有按。

本题可以转化成一个数学问题，将灯的状态表示为一个01矩阵。例如，一个3×3的01矩阵如下：

最初灯的状态表示的矩阵称为初始状态矩阵，记为L。

每次按下按钮时，可以看成在给出的矩阵上进行异或运算，即模2加运算。例如，在上述矩阵中，按下第2行第2列的按钮时，就是将原来的矩阵和如下的矩阵进行异或运算：

这样的矩阵称为作用范围矩阵，用A(i,j)表示按下第i行第j列按钮时的作用范围矩阵。例如，上述的作用范围矩阵记为A(2, 2)。如果按下左上角的按钮，作用范围矩阵记为A(1, 1)。

假设x(i,j)表示要使矩阵L成为零矩阵，第i行第j列的按钮是否需要按下，0表示不按，1表示按下。这样，本题就转化为矩阵方程的求解。可以将上例转换为如下矩阵方程的求解：L⊕x(1, 1)*A(1, 1)⊕x(1, 2)*A(1, 2)⊕x(1, 3)*A(1, 3)⊕x(2, 1)*A(2, 1)⊕…⊕x(3, 3)*A(3, 3)=0。其中x(i,j)是变量，取值为0或1；方程右边的0表示零矩阵，即灯全灭的状态。直观的理解就是：原来的状态L经过了若干个A(i,j)的变换，最终变成零矩阵，也就是灯全灭的状态。

又因为上述矩阵是01矩阵，所以，上述矩阵方程两边异或L，则成为：x(1, 1)*A(1, 1)⊕x(1, 2)*A(1, 2)⊕x(1, 3)*A(1, 3)⊕x(2, 1)*A(2, 1)⊕…⊕x(3, 3)*A(3, 3)=L。

两个矩阵相等的充要条件是矩阵中的每个元素都相等。所以，上述矩阵方程展开，便转化成了一个9元1次方程组。

参考程序

【2.3.3 The Water Bowls】

奶牛们用排成一排的20只水碗来喝水。碗口可以向上（可以盛水）或者向下（无法盛水）。奶牛们希望20只水碗的碗口都朝上。它们可以用鼻子将碗翻转。

然而，它们的鼻子太宽了，在翻转一个碗时，会同时翻转这只碗两边的碗，即：如果翻转的是两端的碗，则翻转两个碗，否则将翻转三个碗。

给出碗的初始状态（1=无法盛水，0=可以盛水），那么要使所有碗的碗口向上，最少要翻转多少次？

输入

输入一行，给出20个由空格分隔的整数。

输出

输出一行，给出要使所有碗的碗口向上（即碗的初始状态都是0），最少要翻转的次数。对于给出的输入，总可以找到某个翻转的组合，翻转产生20个0。

提示

例如，对于样例，只须翻转第4、9、11只碗，便可使得所有的碗都能盛水。

●0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0[初始状态]

●0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0[翻转了第4只碗之后]

●0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0[翻转了第9只碗之后]

●0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0[翻转了第11只碗之后]

试题来源：USACO 2006 January Bronze

在线测试：POJ 3185

试题解析

本题题意为，给出20只碗的初始状态，碗口要么向上（标志为0），要么向下（标志为1）；当翻转一只碗时，其左右的碗也要翻转，要使这些碗全部变成碗口向上的状态，至少需要翻转多少次。

本题和题目2.3.2类似，不同的是题目2.3.2有唯一解，而本题可能会有多组解。首先，和题目2.3.2一样，输入时构造增广矩阵；然后，对增广矩阵进行高斯异或消元，确定是无解、有唯一解，还是有若干自由变量。若有唯一解，则直接求解；若有num个自由变量，则枚举自由变量，由于变量取值为0或1，因此存在2num个自由变量状态，每个状态中num个自由变量对应的方程是阶梯形矩阵最下面的num行，从第n-num-1行到第1行依次回代，便可得到其余变量的值，n个变量值的和即为当前自由变量状态下的翻转次数。2num个自由变量状态中最小的翻转次数即为答案。

参考程序