ac1133.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1133;
const
  maxn=100;
  maxbans=25;
  base=10000;
  hashsize=9999;
  modulo=4999;
type
  bignum=array[-1..40]of longint;
  polynom=array[-1..maxbans+2]of longint;
var
  fac:array[0..maxn]of bignum;
  x,y:array[1..maxbans]of byte;
  bit,filter:array[1..maxbans]of longint;
  hash,next:array[0..hashsize]of word;
  poly:array[0..hashsize]of polynom;
  n,i,j,bans,t,rear,key:longint;
  p:polynom;
  ans,big:bignum;
function ins(a:longint):word;
  begin
    key:=a mod modulo;a:=a div modulo;
    if next[key]>0 then begin
      while next[key]<maxint do key:=next[key];
      next[key]:=rear;key:=rear;inc(rear);
    end;
    hash[key]:=a;poly[key]:=p;next[key]:=maxint;
    ins:=key;
  end;
function find(a:longint):integer;
  begin
    find:=-1;key:=a mod modulo;a:=a div modulo;
    if next[key]=0 then exit;
    repeat
      if hash[key]=a then begin find:=key;exit;end;
      key:=next[key];
    until key=maxint;
  end;
function cal(a,b:longint):integer;
  var
    u,v:word;
  begin
    cal:=find(a);
    if cal>=0 then exit;
    if a>0 then begin
      while a and bit[b]=0 do inc(b);
      u:=cal(a xor bit[b],b+1);
      v:=cal(a and filter[b],b+1);
      p:=poly[u];if poly[v,-1]>=p[-1] then p[-1]:=poly[v,-1]+1;
      for i:=0 to poly[v,-1] do inc(p[i+1],poly[v,i]);
    end
    else begin
      fillchar(p,sizeof(p),0);p[0]:=1;
    end;
    cal:=ins(a);
  end;
procedure add(var a,b:bignum);
  var
    l,i:byte;
  begin
    if a[-1]>b[-1] then l:=a[-1] else l:=b[-1];
    for i:=0 to l do begin
      inc(a[i],b[i]);
      inc(a[i+1],a[i] div base);
      a[i]:=a[i] mod base;
    end;
    a[-1]:=l+ord(a[l+1]>0);
  end;
procedure sub(var a,b:bignum);
  var
    i:byte;
  begin
    for i:=0 to b[-1] do begin
      dec(a[i],b[i]);
      if a[i]<0 then begin
        inc(a[i],base);dec(a[i+1]);
      end;
    end;
    while (a[-1]>0) and (a[a[-1]]=0) do dec(a[-1]);
  end;
procedure mul(var a:bignum;b:longint);
  var
    b1,b2,i:word;
  begin
    b1:=b div base;b2:=b mod base;
    for i:=a[-1] downto 0 do begin
      inc(a[i+1],a[i]*b1);
      a[i]:=a[i]*b2;
    end;
    for i:=0 to a[-1] do begin
      inc(a[i+1],a[i] div base);
      a[i]:=a[i] mod base;
    end;
    while a[a[-1]+1]>0 do begin
      inc(a[-1]);
      a[a[-1]+1]:=a[a[-1]] div base;
      a[a[-1]]:=a[a[-1]] mod base;
    end;
  end;
procedure out(var a:bignum);
  var
    i:shortint;
  begin
    write(a[a[-1]]);
    for i:=a[-1]-1 downto 0 do
      write(a[i] div 1000,a[i] div 100 mod 10,a[i] div 10 mod 10,a[i] mod 10);
    writeln;
  end;
begin
  fac[0,-1]:=0;fac[0,0]:=1;
  for n:=1 to maxn do begin
    fac[n]:=fac[n-1];
    mul(fac[n],n);
  end;

  bit[1]:=1;for i:=2 to maxbans do bit[i]:=bit[i-1]*2;

  repeat
    read(n);bans:=0;
    for i:=1 to n do
      for j:=1 to n do begin
        read(t);
        if t=1 then begin
          inc(bans);x[bans]:=i;y[bans]:=j;
        end;
      end;
    fillchar(filter,sizeof(filter),0);
    for i:=1 to bans do
      for j:=1 to bans do
        if (x[i]<>x[j]) and (y[i]<>y[j]) then filter[i]:=filter[i] or bit[j];

    fillchar(next,sizeof(next),0);rear:=modulo;
    t:=power(2,bans)-1;
    p:=poly[cal(t,1)];

    ans:=fac[n];
    for i:=1 to n shr 1 do begin
      if p[i*2]=0 then break;
      big:=fac[n-i*2];mul(big,p[i*2]);
      add(ans,big);
    end;
    for i:=1 to (n+1) shr 1 do begin
      if p[i*2-1]=0 then break;
      big:=fac[n-i*2+1];mul(big,p[i*2-1]);
      sub(ans,big);
    end;
    out(ans);
  until seekeof;
end.