ac1059.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1059;
const
  half=1500000;
var
  s:array[0..half,0..2]of int64;
  n,i:longint;
  base:int64;
procedure tail(a:int64);
  var
    s:string;
    i:byte;
  begin
    str(a,s);
    for i:=length(s) to 17 do write('0');
    write(s);
  end;
procedure out(a,b,c:int64);
  begin
    if a>0 then begin
      write(a);tail(b);tail(c);
    end
    else if b>0 then begin
      write(b);tail(c);
    end
    else
      write(c);
    writeln;
  end;
begin
  base:=power(10,9);base:=base*base;
  s[0,0]:=1;
  for n:=1 to half do
    for i:=0 to 2 do begin
      inc(s[n,i],s[n-1,i]+s[n shr 1,i]);
      if s[n,i]>=base then begin
        inc(s[n,i+1]);dec(s[n,i],base);
      end;
    end;

  repeat
    read(n);n:=n shr 1;
    out(s[n,2],s[n,1],s[n,0]);
  until seekeof;
end.