LQDDIV - Phân tập
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxs=65536;
max=16000000;
type ar=array[0..maxs] of longint;
var n,m,m1,m2,i,j,k,sum,t,num,q,rem,temp,re:longint; dem:int64;
a:array[0..31] of longint;
b:array[0..15] of longint;
p:array[0..16] of longint;
f,g,sl:ar;
tr:array[0..max] of longint;
npos:longint;
procedure rf;
var i:longint;
begin
assign(input,fi);
reset(input);
p[0]:=1;
for i:=1 to 16 do p[i]:=p[i-1] shl 1;
readln(n);
m:=n div 2-1;
m1:=p[m+1]-1;
sum:=0;
for i:=0 to m do
begin
read(a[i]);
sum:=sum+a[i];
end;
m:=n-n div 2-1;
for i:=0 to m do
begin
read(b[i]);
sum:=sum+b[i];
end;
m2:=p[m+1]-1;
close(input);
end;
procedure wf;
begin
assign(output,fo);
rewrite(output);
write(re,' ',dem);
close(output);
end;
procedure sort(l,r:longint);
var x,y,i,j:longint;
begin
i:=l; j:=r; x:=f[(i+j) div 2];
repeat
while f[i]<x do i:=i+1;
while f[j]>x do j:=j-1;
if i<=j then
begin
y:=f[i]; f[i]:=f[j]; f[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function bs(x:longint;var num:longint):longint;
var l,r,m,y,re,t,u,i:longint;
begin
l:=1; r:=npos; num:=0; y:=-1; re:=maxlongint; bs:=re;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]=x then break;
if f[m]<x then l:=m+1
else r:=m-1;
end;
if rem=0 then
begin
for i:=m-1 to m+1 do
if (i>0) and (i<=npos) and (abs(f[i]-x)<re) then
begin
re:=abs(f[i]-x);
y:=f[i];
end;
if y<>-1 then
begin
bs:=re*2;
t:=tr[y];
num:=sl[t];
if re<>0 then
begin
if (2*x-y<0) or (2*x-y>max) then exit;
t:=tr[2*x-y];
if t>0 then num:=num+sl[t];
end;
end;
end
else
begin
for i:=m-2 to m+2 do
if (i>0) and (i<=npos) then
begin
if f[i]<=x then
begin
if x-f[i]<re then
begin
re:=abs(f[i]-x);
y:=f[i];
end;
end
else
begin
if f[i]-1-x<re then
begin
re:=f[i]-x-1;
y:=f[i];
end;
end;
end;
if y<>-1 then
begin
bs:=2*re+1;
t:=tr[y];
num:=num+sl[t];
if (2*x+1-y<0) or (2*x-y+1>max) then exit;
t:=tr[2*x+1-y];
if t>0 then num:=num+sl[t];
end;
end;
end;
begin
rf;
for i:=1 to m1 do
begin
k:=i; j:=0;
while k>0 do
begin
if k and 1=1 then f[i]:=f[i]+a[j];
j:=j+1;
k:=k shr 1;
end;
end;
sort(0,m1);
g:=f;
npos:=1;
fillchar(f,sizeof(f),0);
f[1]:=0; tr[0]:=1; sl[1]:=1;
for i:=1 to m1 do
if g[i]=g[i-1] then inc(sl[npos])
else
begin
inc(npos);
f[npos]:=g[i];
tr[g[i]]:=npos;
sl[npos]:=1;
end;
re:=maxlongint-10; dem:=0; q:=sum div 2; rem:=sum mod 2;
m2:=m2 shr 1;
for i:=0 to m2 do
begin
k:=i; j:=0; temp:=0;
while k>0 do
begin
if k and 1=1 then temp:=temp+b[j];
j:=j+1;
k:=k shr 1;
end;
t:=bs(q-temp,num);
if t<re then
begin
re:=t;
dem:=num;
end
else
begin
if t=re then dem:=dem+num;
end;
end;
wf;
end.