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.