关于高斯消元解决xor问题的总结

我觉得xor这东西特别神奇，最神奇的就是这个性质了 A xor B xor B=A

这样就根本不用在意重复之类的问题了

关于xor的问题大家可以去膜拜莫队的《高斯消元解XOR方程组》，里面写的很详细

我来扯两道bzoj上的例题好了

bzoj2115，求1-N最长xor路径，根据那个神奇的性质，我们先随便找一条1-n的路径作为标准路径

任意一条1-N的路径都等价于标准路径和某些环的xor

怎么找环？很简单，bfs下去，设d[x]表示1到x的一条路径xor值，如果到一条边x-->y时y已经访问过了，那么d[x] xor d[y] xor w[x,y]就是一个环

然后这个问题就转变成了求一堆数中任意数xor最大的问题，这我们是通过求线性基然后按位贪心就可以了

type node=record
       po,next:longint;
       num:int64;
     end;

var f:array[0..64] of int64;
    d:array[0..50010] of int64;
    q,p:array[0..50010] of int64;
    a:array[0..500010] of int64;
    e:array[0..200010] of node;
    x,y,i,n,m,len,t:longint;
    ans,z:int64;

procedure add(x,y:longint;z:int64);
  begin
    inc(len);
    e[len].po:=y;
    e[len].num:=z;
    e[len].next:=p[x];
    p[x]:=len;
  end;

procedure bfs;
  var h,r,i,x,y:longint;
  begin
    fillchar(d,sizeof(d),255);
    d[1]:=0;
    h:=1; r:=1; q[1]:=1;
    while h<=r do
    begin
      x:=q[h];
      i:=p[x];
      while i<>0 do
      begin
        y:=e[i].po;
        if d[y]=-1 then
        begin
          d[y]:=d[x] xor e[i].num;
          inc(r);
          q[r]:=y;
        end
        else if d[y] xor d[x] xor e[i].num<>0 then  //找环
        begin
          inc(t);
          a[t]:=d[y] xor d[x] xor e[i].num;
        end;
        i:=e[i].next;
      end;
      inc(h);
    end;
  end;

procedure gauss;
  var i,j:longint;
  begin
    for i:=1 to t do
      for j:=60 downto 0 do
        if a[i] and (int64(1) shl j)>0 then //求线性基
        begin
          if f[j]=0 then
          begin
            f[j]:=a[i];
            break;
          end
          else a[i]:=a[i] xor f[j];
        end;

    ans:=d[n];
    for i:=60 downto 0 do
      if ans and (int64(1) shl i)=0 then ans:=ans xor f[i];
  end;

begin
  readln(n,m);
  for i:=1 to m do
  begin
    readln(x,y,z);
    add(x,y,z);
    add(y,x,z);
  end;
  bfs;
  gauss;
  writeln(ans);
end.

bzoj2844

一堆数xor能产生数的种类数就是2^线性基的秩

并且每个数出现的次数是一样的（求证明）

然后我们就可以做了，注意这里的线性基要用高斯消元求而不能用上题的方法

因为要计算某个数出现在第几位，必须使线性基相互xor的数的大小满足二进制位的大小关系

举个例子，比如线性基a,b,c并且a>b>c，如果取a,b xor，选取状况为110，这样选取xor的数一定要比011这样选大，我们称之为满足二进制大小关系（我自己口胡的名词）

const mo=10086;

var a,d:array[0..100010] of longint;
    f,b:array[0..40] of longint;
    k,p,i,j,n,ans,m,t:longint;

procedure swap(var a,b:longint);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

begin
  readln(n);
  for i:=1 to n do
    read(a[i]);
  d[0]:=1;
  for i:=1 to n do
    d[i]:=d[i-1]*2 mod mo;

  readln(m);
  k:=n;
  for i:=1 to n do
  begin
    for j:=i+1 to n do
      if a[i]<a[j] then swap(a[i],a[j]);
    if a[i]=0 then
    begin
      k:=i-1;
      break;
    end;
    for j:=30 downto 0 do
      if a[i] and (1 shl j)>0 then
      begin
        b[i]:=j;
        for p:=1 to n do
          if (p<>i) and (a[p] and (1 shl j)>0) then
            a[p]:=a[p] xor a[i];
        break;
      end;
  end;
  ans:=1;
  for i:=1 to k do
    if m and (1 shl b[i])>0 then
    begin
      m:=m xor a[i];
      ans:=(ans+d[k-i+n-k]) mod mo;
    end;

  writeln(ans);
end.