POJ 1830（位运算+双向DFS）

此题也可用GE做，可是我不会矩阵乘法……

[delphi] 
Program P1830; 
const 
   maxn=28; 
   maxf=100007; 
   none=-2139062144; 
var 
   ans,tt,n,i,j,s,t,mid:longint; 
   b:array[1..29] of longint; 
   h,num:array[0..maxf] of longint; 
 
function hash(x:longint):longint; 
var 
   i,j:longint; 
begin 
   hash:=x mod maxf; 
   while (num[hash]<>x) and (num[hash]<>none) do 
   begin 
      hash:=(hash+1) mod maxf; 
   end; 
   num[hash]:=x; 
   exit(hash); 
end; 
procedure dfs(x,l:longint); 
var 
   i,j:longint; 
begin 
   if l=mid+1 then 
   begin 
      inc(h[hash(x)]); 
      exit; 
   end; 
   for i:=l to mid do 
      dfs(x xor b[i],i+1); 
   dfs(x,mid+1); 
 
end; 
procedure find(x,l:longint); 
var 
   i,j:longint; 
begin 
   if l=n+1 then 
   begin 
      inc(ans,h[hash(x)]); 
      exit; 
   end; 
   for i:=l to n do 
      find(x xor b[i],i+1); 
   find(x,n+1); 
 
end; 
 
begin 
   read(tt); 
   while (tt>0) do 
   begin 
      ans:=0; 
      fillchar(b,sizeof(b),0); 
      fillchar(num,sizeof(num),128); 
      fillchar(h,sizeof(h),0); 
 
      read(n); 
      s:=0; 
      for i:=1 to n do 
      begin 
         read(j); 
         if j=1 then inc(s,1 shl (i-1)); 
      end; 
      t:=0; 
      for i:=1 to n do 
      begin 
         read(j); 
         if j=1 then inc(t,1 shl (i-1)); 
      end; 
      while (true) do 
      begin 
         read(i,j); 
         if (i=0) and (j=0) then break; 
         inc(b[i],1 shl (j-1)); 
      end; 
      for i:=1 to n do inc(b[i],1 shl (i-1)); 
      mid:=n shr 1; 
      dfs(s,1); 
      find(t,mid+1); 
      if ans=0 then writeln('Oh,it''s impossible~!!') else 
      writeln(ans); 
      dec(tt); 
   end; 
end.