状态压缩小结

program cowfood;
var
  a,b:array[0..4096]of int64;
  f:array[0..12,0..4096]of int64;
  n,m,x,t,len,ans:int64; i,j,k:longint;
procedure work;
var i:longint;
begin
 len:=0;
  for i:=0 to 1 shl m-1 do
   if (i and (i<<1))=0 then begin  inc(len);  b[len]:=i; end;
end;
function cheak(x,y:longint):boolean;
begin
  if (a[x] and b[y])=0 then exit(true) else exit(false);
end;
begin
  assign(input,‘cowfood.in‘);
  reset(input);
  assign(output,‘cowfood.out‘);
  rewrite(output);
  readln(n,m);
  k:=1 shl (m-1);
  for i:=1 to n do
   begin   t:=k;
     for j:=1 to m do
      begin
        read(x);inc(a[i],t*(1-x));  t:=t shr 1;
      end;
     readln;
   end;
 work;
  for i:=1 to len do  if cheak(1,i) then f[1,b[i]]:=1;
  for i:=2 to n do
   for j:=1 to len do
    if cheak(i,j) then
     for k:=1 to len do
        if (b[j]and b[k]=0)and(cheak(i-1,k))  then
         f[i,b[j]]:=(f[i,b[j]]+f[i-1,b[k]])mod 100000000;
  for i:=1 to len do
  ans:=(ans+f[n,b[i]])mod 100000000;
  writeln(ans);
  close(input); close(output);
end.