【异或(XOR)运算由于与“奇偶性”密切相关,经常出现在有关奇偶性和二进制的题目中】
很多异或问题都要涉及到解异或方程组,因此首先要搞懂异或方程组的解法。

(1)异或方程组的格式(设有n个未知数,m个方程):
a11*x1 XOR a12*x2 XOR ... XOR a1n*xn = b1
a21*x1 XOR a22*x2 XOR ... XOR a2n*xn = b2
……………………………………………………
am1*x1 XOR am2*x2 XOR ... XOR amn*xn = bm
其中的所有a、b、x的值均为0或1。解异或方程组就是给出了所有的系数a和b之后,求出解(x1, x2 ... xn)。一般来说,题目的要求无非就是如下几种:<1>求任意一组解;<2>求解的总数;<3>求出最优解(比如字典序最小的解或者加权以后权值最大/小的解等)。

(2)求解异或方程组的离线算法:
整体思想与普通方程组的高斯消元解法类似。
第一阶段(消元):设置一个变量p,一开始p=1,然后,i从1到n,每次执行:<1>若在第p个及以后的方程中,至少有一个方程的xi系数为1,设为第q个方程,则先将第p、q个方程交换,然后用第p个方程去XOR后面剩下的所有xi系数为1的方程(各系数包括b都对应进行XOR运算,实际上就是矩阵初等行变换),将它们的xi系数均变成0,最后p加1;<2>否则(第p个及以后的方程中xi系数均为0),xi是自由元(xi不管是取0还是1,都能导出整个方程组的一个解),按照自由元处理(随便定值,然后将前面所有xi系数为1的方程全部代入xi的值XOR掉),p值不变。(感谢HN SYJ神犇,在总结中讲到了如果遇到自由元的话p值是不能变的,否则会疵,见这里
第二阶段(回代求解):在第一阶段结束后,若出现了S个自由元,则会在整个方程组的最后出现S个多余方程,它们的等号左边所有系数均为0(显然值也为0)。对于这些多余方程,如果有等号右边为1的,则整个方程组无解。否则,如果所有多余方程的等号右边均为0,则整个方程组有2S个解(因为S个自由元可以随便取值,都能导出解)。如果要求具体的解,则从第(m-S)个方程开始,往回代,设立变量p,初始p=m-S,逆序枚举每个未知数(自由元除外),对于未知数xi,可以从第p个方程中直接得到其值(因为此时第p个方程等号左边必然只有xi系数为1,等号右边是几,xi值就是几),然后,将之前的所有xi系数为1的方程全部用第p个方程XOR掉,p--。
具体实现的时候有一些技巧:
1)在第一阶段第<1>步XOR的时候,实际上只要枚举xi及其后面的未知数就行了,因为前面的未知数已经消掉了;在第<2>步XOR的时候,只需要xi和等号右边的系数b,因为其它的系数均为0;
2)第一阶段的p可以直接留到第二阶段继续用,只不过要减1。

(3)求解异或方程组的在线算法:
这里的在线算法其实指的是,它可以随时在后面增加新的方程,直接扩展已求出的解以及更新解的总数,而不用每次重新求解。这个算法在某些求”XOR值最大“的问题中显然比较有用。
为了讲清楚这个算法,首先要引入”关键元“:在消元过程中,每个方程有至多一个”关键元“,它决定了该方程可以去XOR后面的哪种方程。设C[i]为关键元为xi的方程编号,若C[i]==-1(以xi为关键元的方程不存在),则xi为自由元,反之亦然。一开始,所有的C值均为-1。
在新加入一个方程时,i从1到n枚举,若该方程xi系数为1,则看一下C[i]是否为-1,若为-1,则xi为该方程关键元,C[i]设为该方程编号,结束(此时,xi不再是自由元,因此整个方程组解的总数减半);若不为-1,则用编号C[i]的方程去XOR该方程(其实只要XOR xi及其之后的部分),将该方程中的xi消去。如果最终i枚举到n时仍然木有找到关键元,则该方程无关键元,也就是说该方程是一个多余方程(0=0或0=1),如果是0=0,则不影响解的总数,如果是0=1,则整个方程组无解了。
如果要求具体的解,则与离线算法的第二阶段类似,只是回代求解时,p不能再是逆序的了,而应该是每个C[i]的值。此外,对于C[i]==-1的(即xi是自由元),随便定值,并代到所有方程中XOR掉它。

显然,以上两种算法的时间复杂度均为O(n2m)。

(4)算法常数优化——压位:
在具体实现的时候,需要用一个bool矩阵A[m][n+1]来存储所有的系数(a、b),这样很浪费,因为完全可以用一个int矩阵,一下存储32位。这种压位思想可以带来常数上的优化,因为在用一个方程去XOR另一个时,时间将变为原来的1/32。
实现起来比不压位的要麻烦一些。具体来说,首先,调用原矩阵的第i行第j列是否为1需要写成A[i][j/32] & (1 << (j % 32))(原矩阵第i行第j列为0当且仅当该值为0),对于等号右边的b系数,在原矩阵中为第n列,因此写成A[i][n/32] & (1 << (n % 32))。在实现过程中,为了避免重复计算,可以设n0=n/32,q=n%32,q0=j/32,q1=j%32,n0和q预先算出,在枚举j(未知数编号)时维护q0、q1。
另外需要严重注意的是:在求出了某个未知数xi的值之后代入到其它方程中时,如果是单个代入不整体XOR,则i和n列都要处理,但如果是整体XOR,则要特判一下i和n列在压位之后是否压到同一位里了,若压到同一位里则只能XOR一次!!!!!!!!!
(其实是可以压64位的,但由于long long的常数较大且在求1<<q时还要强制类型转换,所以得不偿失,不如压32位快)

例题:JSOI2012 arc
建模方法:设一组解(x1, x2 ... xn)为:xi==0当且仅当i在上游。对于原图中给出的有向图,若i的出度为偶数,则需要满足i指向的那些点的x值XOR之和为0即可(不管xi是0还是1);若i的出度为奇数,则需要满足i及其指向的那些点的x值的XOR之和为1即可(不管xi是0还是1)。这样就转化为求异或方程组的特解问题,假设在求解过程中,对于所有的自由元均定为0。
代码(均为压位之后的):
离线算法:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<time.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 2005, KS = 32, MAXN0 = (MAXN + 1/ KS + 1, INF = ~0U >> 2;
int n, n0, q, A[MAXN][MAXN0];
bool res[MAXN], res_ex = 1;
void init()
{
    freopen(
"arc.in""r", stdin);
    
int q0 = 0, q1 = 0, x, y;
    scanf(
"%d"&n); n0 = n / KS; q = n % KS;
    re(i, n) {
        scanf(
"%d"&x);
        
if (x & 1) {A[i][q0] |= 1 << q1; A[i][n0] |= 1 << q;}
        re(j, x) {scanf(
"%d"&y); y--; A[i][y / KS] |= 1 << (y % KS);}
        
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
    }
    fclose(stdin);
}
void solve()
{
    
int q0 = 0, q1 = 0, p = 0, x;
    ll tmp;
    re(i, n) {
        x 
= -1;
        re2(j, p, n) 
if (A[j][q0] & (1 << q1)) {x = j; break;}
        
if (x >= 0) {
            
if (x != p) {re3(k, q0, n0) {tmp = A[x][k]; A[x][k] = A[p][k]; A[p][k] = tmp;}}
            re2(j, p
+1, n) if (A[j][q0] & (1 << q1)) re3(k, q0, n0) A[j][k] ^= A[p][k];
            p
++;
        } 
else {
            res[i] 
= 1;
            re(j, p) 
if (A[j][q0] & (1 << q1)) {A[j][q0] &= ~(1 << q1); A[j][n0] ^= 1 << q;}
        }
        
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
    }
    re2(i, p, n) 
if (A[i][n0] & (1 << q)) {res_ex = 0return;} p--;
    rre(i, n) {
        
if (q1) q1--else {q0--; q1 = KS - 1;}
        
if (!res[i]) {
            res[i] 
= A[p][n0] & (1 << q);
            re(j, p) 
if (A[j][q0] & (1 << q1)) {
                A[j][q0] 
^= A[p][q0]; if (q0 < n0) A[j][n0] ^= A[p][n0];
            }
            p
--;
        }
    }
}
void pri()
{
    freopen(
"arc.out""w", stdout);
    
if (res_ex) {
        
int sum = 0bool SPC = 0;
        re(i, n) 
if (!res[i]) sum++;
        printf(
"%d\n", sum);
        re(i, n) 
if (!res[i]) {
            
if (SPC) putchar(' '); else SPC = 1;
            printf(
"%d", i + 1);
        }
        puts(
"");
    } 
else puts("Impossible");
    fclose(stdout);
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}
在线算法:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 2005, KS = 32, MAXN0 = (MAXN + 1/ KS + 1, INF = ~0U >> 2;
int n, n0, q, A[MAXN][MAXN0], B[MAXN];
bool C[MAXN], res[MAXN], res_ex = 1;
void init()
{
    freopen(
"arc.in""r", stdin);
    
int q0 = 0, q1 = 0, x, y, _q0, _q1;
    scanf(
"%d"&n); n0 = n / KS; q = n % KS;
    re(i, n) {
        scanf(
"%d"&x);
        
if (x & 1) {A[i][q0] |= 1 << q1; A[i][n0] |= 1 << q;}
        re(j, x) {
            scanf(
"%d"&y); y--; _q0 = y / KS; _q1 = y % KS;
            A[i][_q0] 
|= 1 << _q1;
        }
        
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
    }
    fclose(stdin);
}
void solve()
{
    re(i, n) B[i] 
= -1;
    
int q0, q1, x;
    re(i, n) {
        q0 
= q1 = 0;
        re(j, n) {
            
if (A[i][q0] & (1 << q1)) {
                x 
= B[j];
                
if (x == -1) {B[j] = i; break;} else re3(k, q0, n0) A[i][k] ^= A[x][k];
            }
            
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
        }
    }
    q0 
= n0; q1 = q;
    rre(i, n) {
        
if (q1) q1--else {q0--; q1 = KS - 1;}
        
if ((x = B[i]) >= 0) {
            res[i] 
= A[x][n0] & (1 << q);
            re(j, n) 
if (j != x && (A[j][q0] & (1 << q1))) {
                A[j][q0] 
^= A[x][q0]; if (q0 < n0) A[j][n0] ^= A[x][n0];
            }
        } 
else {
            res[i] 
= 1;
            re(j, n) 
if (A[j][q0] & (1 << q1)) {
                A[j][q0] 
&= ~(1 << q1); A[j][n0] ^= 1 << q;
            }
        }
    }
    re(i, n) 
if ((x = B[i]) >= 0) C[x] = 1;
    re(i, n) 
if (!C[i] && (A[i][n0] & (1 << q))) {res_ex = 0return;}
}
void pri()
{
    freopen(
"arc.out""w", stdout);
    
if (res_ex) {
        
int sum = 0bool SPC = 0; re(i, n) if (!res[i]) sum++;
        printf(
"%d\n", sum);
        re(i, n) 
if (!res[i]) {
            
if (SPC) putchar(' '); else SPC = 1;
            printf(
"%d", i + 1);
        }
        puts(
"");
    } 
else puts("Impossible");
    fclose(stdout);
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}

Feedback

# re: XOR专题(一):异或方程组的解法  回复  更多评论   

2012-05-20 15:10 by lx99410
你有JSOI2012题目与数据吗?,能否发给我?邮箱:lixiang99410@126.com,不胜感激!

# re: XOR专题(一):异或方程组的解法  回复  更多评论   

2012-05-22 17:00 by olyminfo
同求

olyminfo@gmail.com

# re: XOR专题(一):异或方程组的解法  回复  更多评论   

2012-06-20 12:38 by wrz
同求
参加了,但是忘了拷了
wrz_10@126.com

# re: XOR专题(一):异或方程组的解法  回复  更多评论   

2014-06-09 00:24 by AHdoc
您应该自豪的告诉别人: (1)这个题目是2010年合肥一中&芜湖安师大附中友谊赛的题目..(2)被傻逼的AHdoc出到JSOI去了..=_=

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理