2.3 高斯消元法求解異或方程組

異或（eXclusive OR, XOR）是一個邏輯運(yùn)算符，異或的數(shù)學(xué)符號為“⊕”，運(yùn)算法則為0⊕0=0、1⊕0=1、0⊕1=1、1⊕1=0，即同為0、異為1。

按位異或是指參與運(yùn)算的兩個值，如果兩個相應(yīng)的二進(jìn)制位相同，則結(jié)果為0，否則結(jié)果為1。C、C++、Java的按位異或運(yùn)算符為“^”，例如，10100001^00000110=10100111。

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

高斯消元法求解異或方程組的方法如下。異或方程組對應(yīng)的增廣矩陣用二維數(shù)組a表示。對于k=1,…,n，找到a[i][k]不為0的行i，將該行與第k行交換；然后，用第k行去異或第k行下面所有a[i][j]不為0的行i，消去它們的第k個系數(shù)，這樣就將原來的增廣矩陣轉(zhuǎn)換成上三角矩陣。

由于最后一行只有一個變量，求出這個變量，然后用它跟上面所有含有該變量的方程異或，以此類推即可自下而上求出所有變量。

下面給出高斯消元法求解異或方程組的程序模板。

題目2.3.1、題目2.3.2和題目2.3.3是應(yīng)用高斯消元法求異或方程組的范例。

【2.3.1 開關(guān)問題】

有N個相同的開關(guān)，每個開關(guān)都與某些開關(guān)有著聯(lián)系，每當(dāng)你打開或者關(guān)閉某個開關(guān)時，其他與此開關(guān)相關(guān)聯(lián)的開關(guān)也會相應(yīng)地發(fā)生變化，即這些互相聯(lián)系的開關(guān)的狀態(tài)如果原來為開就變?yōu)殛P(guān)，如果為關(guān)就變?yōu)殚_。你的目標(biāo)是經(jīng)過若干次開關(guān)操作后使最后N個開關(guān)達(dá)到一個特定的狀態(tài)。對于任意一個開關(guān)，最多只能進(jìn)行一次開關(guān)操作。你的任務(wù)是計(jì)算有多少種可以達(dá)到指定狀態(tài)的方法。（不計(jì)開關(guān)操作的順序。）

輸入

輸入的第一行有一個數(shù)K，表示以下有K組測試數(shù)據(jù)。

每組測試數(shù)據(jù)的格式如下。

●第一行，一個數(shù)N(0<N<29)。

●第二行，N個為0或者1的數(shù)，表示開始時N個開關(guān)的狀態(tài)。

●第三行，N個為0或者1的數(shù)，表示操作結(jié)束后N個開關(guān)的狀態(tài)。

接下來，每行兩個數(shù)I、J，表示如果操作第I個開關(guān)，第J個開關(guān)的狀態(tài)也會變化。每組數(shù)據(jù)以“00”結(jié)束。

輸出

如果有可行方法，輸出總數(shù)，否則輸出“Oh, it’s impossible～!!”（不包括引號）。

提示

對于第一組數(shù)據(jù)，共有以下四種操作方法：操作開關(guān)1；操作開關(guān)2；操作開關(guān)3；操作開關(guān)1、2、3（不記順序）。

試題來源：LIANGLIANG@POJ

在線測試：POJ 1830

試題解析

本題要求計(jì)算開關(guān)從初始狀態(tài)變到目標(biāo)狀態(tài)有多少種變換方式。

設(shè)n×n方陣A表示n個開關(guān)的關(guān)聯(lián)關(guān)系，方陣A的列向量Ai表示變換第i個開關(guān)會影響到哪些開關(guān)，A[j][i]=1表示變換第i個開關(guān)的操作能夠影響第j個開關(guān)的狀態(tài)，而A[j][i]=0則表示變換第i個開關(guān)的操作不會影響第j個開關(guān)的狀態(tài)；顯然，A[i][i]=1。列向量X表示開關(guān)的操作，X[i]取值為1或者0，分別表示第i個開關(guān)變換或者不變換。列向量B表示初始狀態(tài)和目標(biāo)狀態(tài)異或運(yùn)算的結(jié)果。

所以，如果A[j][i]=1，且X[i]=1，則A[j][i]×X[i]=1，表示第i個開關(guān)的狀態(tài)改變；如果A[j][i]=0，則A[j][i]×X[i]=0，表示第i個開關(guān)的狀態(tài)不變；如果X[i]==0，表示不對第i個開關(guān)操作，則對第j個開關(guān)的狀態(tài)也沒有影響，即A[j][i]×X[i]=0，此時第i個開關(guān)狀態(tài)不變。則A[j][1]×X[1]⊕A[j][2]×X[2]⊕…⊕A[j][n]×X[n]=B[j]，1≤j≤n。

本題求解用異或方程組AX=B表示，然后進(jìn)行高斯消元求解。

當(dāng)化簡后增廣矩陣的秩等于原矩陣的秩且等于n時，即化簡后為絕對的上三角矩陣，X有唯一解；當(dāng)化簡后增廣矩陣的秩等于原矩陣的秩且小于n時，有多組解；設(shè)自由變量有y個，可行方法的總數(shù)為2y；當(dāng)化簡后增廣矩陣的秩與原矩陣的秩不相等時，即增廣矩陣化簡后存在（0, 0, 0,…, a）的情況，則無解。

例如，對于樣例輸入的第一組數(shù)據(jù)，方陣A是全1陣，矩陣運(yùn)算表示為=，即相應(yīng)的異或方程組為，則增廣矩陣為；所以，自由變量有2個，可行方法的總數(shù)為22=4。

對于樣例輸入的第二組數(shù)據(jù)，矩陣運(yùn)算表示為，則相應(yīng)的異或方程組為，則增廣矩陣為，由矩陣第2行可知，得無解。

參考程序

【2.3.2 Extended Lights Out】

游戲Lights Out的擴(kuò)展版本是一個5行、每行6個按鈕的智力游戲面板（實(shí)際上，游戲是5行，每行5個按鈕），每個按鈕也都是燈。當(dāng)一個按鈕被按下時，該按鈕及其上、下、左、右（最多四個）相鄰按鈕的燈的狀態(tài)都會反轉(zhuǎn)，即：如果原來燈開著，就關(guān)燈；如果燈關(guān)著，就開燈。如果按下面板角落上的按鈕，則改變相應(yīng)的3個按鈕的狀態(tài)；如果按下邊上的按鈕，則改變相應(yīng)的4個按鈕的狀態(tài)；按下其他按鈕，則改變相應(yīng)的5個按鈕的狀態(tài)。例如，在圖2.3-1中，如果按下左側(cè)游戲面板中標(biāo)有×的按鈕，則游戲面板變?yōu)橛覀?cè)的面板。

這個游戲從面板上一組初始的燈的狀態(tài)開始，通過按下按鈕，使面板上所有的燈都關(guān)上。當(dāng)按下相鄰的按鈕時，一次按鈕可以抵消另一次按鈕所產(chǎn)生的效果。例如，在圖2.3-2所示的實(shí)例中，按左側(cè)面板上標(biāo)記×的按鈕，將產(chǎn)生右側(cè)的面板狀態(tài)。這里要注意，第2行第3列和第2行第5列的按鈕都改變了第2行第4列的按鈕的狀態(tài)，因此，最終該按鈕的狀態(tài)不變。

這里要注意以下幾點(diǎn)。

●按下按鈕的順序無關(guān)緊要。

●如果一個按鈕被第二次按下，將完全抵消第一次按下該按鈕的效果，因此任何按鈕都不需要被多次按下。

●如圖2.3-2所示，通過按下第2行中的相應(yīng)按鈕，可以關(guān)上第一行中的所有燈。通過在每一行重復(fù)這一過程，前4行中的所有燈都能關(guān)上。同樣，按第2, 3,…列中的按鈕，前5列中的所有燈都可以被關(guān)上。

請編寫一個程序解這個游戲。

輸入

輸入的第一行是一個正整數(shù)n，給出后面的游戲面板數(shù)。每個面板是5行，每行有6個由一個或多個空格隔開的0或1，其中，0表示燈已關(guān)，1表示燈開著。

輸出

對于每個游戲面板，首先，輸出一行字符串“PUZZLE #m”，其中m是輸入中游戲面板的序號。在這一行之后是一個類似游戲面板的展示（與輸入的格式相同），在展示中，1表示要解該游戲，必須按下這一位置的按鈕，而0表示不要按下相應(yīng)的按鈕。在輸出的面板顯示中，每個0或1之間要正好有一個空格。

試題來源：ACM Greater New York 2002

在線測試：POJ 1222，UVA 2561

試題解析

本題給出一個5×6的矩陣，矩陣中的每個值都表示相應(yīng)位置的按鈕燈的狀態(tài)，1表示燈亮，0表示燈滅。每當(dāng)按下一個位置的按鈕，它和它相鄰的燈的狀態(tài)全部翻轉(zhuǎn)。在這樣的矩陣中，按下哪些按鈕可以把整個矩陣都變成燈滅，1表示按了，0表示沒按。其中，按按鈕的順序可以是任意的，而且，任何一個按鈕都最多只需要按下一次，因?yàn)榘聪碌诙蝿偤玫窒谝淮危扔跊]有按。

本題可以轉(zhuǎn)化成一個數(shù)學(xué)問題，將燈的狀態(tài)表示為一個01矩陣。例如，一個3×3的01矩陣如下：

最初燈的狀態(tài)表示的矩陣稱為初始狀態(tài)矩陣，記為L。

每次按下按鈕時，可以看成在給出的矩陣上進(jìn)行異或運(yùn)算，即模2加運(yùn)算。例如，在上述矩陣中，按下第2行第2列的按鈕時，就是將原來的矩陣和如下的矩陣進(jìn)行異或運(yùn)算：

這樣的矩陣稱為作用范圍矩陣，用A(i,j)表示按下第i行第j列按鈕時的作用范圍矩陣。例如，上述的作用范圍矩陣記為A(2, 2)。如果按下左上角的按鈕，作用范圍矩陣記為A(1, 1)。

假設(shè)x(i,j)表示要使矩陣L成為零矩陣，第i行第j列的按鈕是否需要按下，0表示不按，1表示按下。這樣，本題就轉(zhuǎn)化為矩陣方程的求解。可以將上例轉(zhuǎn)換為如下矩陣方程的求解：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表示零矩陣，即燈全滅的狀態(tài)。直觀的理解就是：原來的狀態(tài)L經(jīng)過了若干個A(i,j)的變換，最終變成零矩陣，也就是燈全滅的狀態(tài)。

又因?yàn)樯鲜鼍仃囀?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)=L。

兩個矩陣相等的充要條件是矩陣中的每個元素都相等。所以，上述矩陣方程展開，便轉(zhuǎn)化成了一個9元1次方程組。

參考程序

【2.3.3 The Water Bowls】

奶牛們用排成一排的20只水碗來喝水。碗口可以向上（可以盛水）或者向下（無法盛水）。奶牛們希望20只水碗的碗口都朝上。它們可以用鼻子將碗翻轉(zhuǎn)。

然而，它們的鼻子太寬了，在翻轉(zhuǎn)一個碗時，會同時翻轉(zhuǎn)這只碗兩邊的碗，即：如果翻轉(zhuǎn)的是兩端的碗，則翻轉(zhuǎn)兩個碗，否則將翻轉(zhuǎn)三個碗。

給出碗的初始狀態(tài)（1=無法盛水，0=可以盛水），那么要使所有碗的碗口向上，最少要翻轉(zhuǎn)多少次？

輸入

輸入一行，給出20個由空格分隔的整數(shù)。

輸出

輸出一行，給出要使所有碗的碗口向上（即碗的初始狀態(tài)都是0），最少要翻轉(zhuǎn)的次數(shù)。對于給出的輸入，總可以找到某個翻轉(zhuǎn)的組合，翻轉(zhuǎn)產(chǎn)生20個0。

提示

例如，對于樣例，只須翻轉(zhuǎn)第4、9、11只碗，便可使得所有的碗都能盛水。

●0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0[初始狀態(tài)]

●0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0[翻轉(zhuǎn)了第4只碗之后]

●0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0[翻轉(zhuǎn)了第9只碗之后]

●0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0[翻轉(zhuǎn)了第11只碗之后]

試題來源：USACO 2006 January Bronze

在線測試：POJ 3185

試題解析

本題題意為，給出20只碗的初始狀態(tài)，碗口要么向上（標(biāo)志為0），要么向下（標(biāo)志為1）；當(dāng)翻轉(zhuǎn)一只碗時，其左右的碗也要翻轉(zhuǎn)，要使這些碗全部變成碗口向上的狀態(tài)，至少需要翻轉(zhuǎn)多少次。

本題和題目2.3.2類似，不同的是題目2.3.2有唯一解，而本題可能會有多組解。首先，和題目2.3.2一樣，輸入時構(gòu)造增廣矩陣；然后，對增廣矩陣進(jìn)行高斯異或消元，確定是無解、有唯一解，還是有若干自由變量。若有唯一解，則直接求解；若有num個自由變量，則枚舉自由變量，由于變量取值為0或1，因此存在2num個自由變量狀態(tài)，每個狀態(tài)中num個自由變量對應(yīng)的方程是階梯形矩陣最下面的num行，從第n-num-1行到第1行依次回代，便可得到其余變量的值，n個變量值的和即為當(dāng)前自由變量狀態(tài)下的翻轉(zhuǎn)次數(shù)。2num個自由變量狀態(tài)中最小的翻轉(zhuǎn)次數(shù)即為答案。

參考程序