LQDRECT - Đếm hình chữ nhật

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$R-,Q-}
{$Mode objfpc}
{$inline on}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXM          =       1024;
  MAXN          =       333;

var
  f1,f2         :       text;
  m,n           :       longint;
  a             :       array[1..MAXM,1..MAXN] of longint;
  save          :       array[0..65536] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i,j:longint;
    begin
      read(f1,m,n);
      for i:=1 to m do
      for j:=1 to n do
        read(f1,a[i,j]);
      while m and 15<>0 do inc(m);
    end;

procedure init;
    var
      k,i,bit,j:longint;
    begin
      for i:=0 to 65535 do
      for bit:=0 to 15 do
        if (i>>bit) and 1=1 then inc(save[i]);

      for i:=1 to m do
      if i and 15=1 then
        for j:=1 to n do
          begin
            for k:=i+1 to i+15 do
              a[i,j]:=a[i,j]<<1+a[k,j];
          end;
    end;

procedure solve;
    var
      u,v,i,x,count:longint;
      res:int64;
    begin
      res:=0;
      for u:=1 to n-1 do
      for v:=u+1 to n do
        begin
          count:=0;
          i:=1;
          while (i<=m) do
            begin
              x:=a[i,u] and a[i,v];
              inc(count,save[x]);
              inc(i,16);
            end;
          inc(res,((count-1)*count)>>1);
        end;
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Download