subset.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:subset
}

program subset;
const
  maxn=39;
var
  fin,fout:text;
  way:array[1..maxn*(maxn+1) div 4]of longint;
  n,goal,i,j:integer;
procedure out(ans:longint);
  begin
    assign(fout,'subset.out');
    rewrite(fout);
    writeln(fout,ans);
    close(fout);
    halt;
  end;
begin
  assign(fin,'subset.in');
  reset(fin);
  readln(fin,n);
  close(fin);

  if odd(n*(n+1) div 2) then out(0);

  goal:=n*(n+1) div 4;
  fillchar(way,sizeof(way),0);
  way[n]:=1;
  for i:=1 to n-1 do
    for j:=goal-i downto n do
      inc(way[j+i],way[j]);

  out(way[goal]);
end.