vans.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:vans
}

{Denote by a[i] the number of routes where the upper left and bottom left
   corners are connected by a straight line.
 Denote by b[i] the number of routes where the upper left and bottom left
   corners are not connected by a straight line.
 So we have:
   b[i]=a[i-1]+b[i-1]
   a[i]=2+a[i-2]+2(a[i-2]+b[i-2]+a[i-1]+b[i-1]+...)
       =2+a[i-2]+2(b[i-1]+b[i-2]+...)
     (the value in the bracket is stored in s)
   The answer is a[n]+b[n]}
program vans;
const
  maxn=1000;
  base=1000000000;
type
  bignum=array[-1..45]of longint;
var
  fin,fout:text;
  a,b:array[1..maxn]of bignum;
  s:bignum;
  n,i:word;
procedure add(var a,b:bignum);
  var
    i:word;
  begin
    if b[-1]>a[-1] then a[-1]:=b[-1];
    for i:=0 to a[-1] do begin
      inc(a[i],b[i]);
      if a[i]>=base then begin
        inc(a[i+1]);dec(a[i],base);
      end;
    end;
    if a[a[-1]+1]>0 then inc(a[-1]);
  end;
procedure out(a:bignum);
  var
    i,j:integer;
    s:string;
  begin
    write(fout,a[a[-1]]);
    for i:=a[-1]-1 downto 0 do begin
      str(a[i],s);
      for j:=length(s) to 8 do write(fout,0);
      write(fout,s);
    end;
    writeln(fout);
  end;
begin
  assign(fin,'vans.in');
  reset(fin);
  read(fin,n);
  close(fin);

  fillchar(a,sizeof(a),0);a[2,0]:=2;
  fillchar(b,sizeof(b),0);
  fillchar(s,sizeof(s),0);
  for i:=3 to n do begin
    add(s,b[i-1]);
    a[i,0]:=2;add(a[i],a[i-2]);add(a[i],s);add(a[i],s);
    b[i]:=a[i-1];add(b[i],b[i-1]);
  end;

  assign(fout,'vans.out');
  rewrite(fout);
  s:=a[n];add(s,b[n]);out(s);
  close(fout);
end.