NKTOSS - Tung đồng xu

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10000;
  oo=100000000;
type
  big=array[0..400] of longint;
var
  f1,f2:text;
  n,k:longint;
  d:array[-1..MAXN] of big;
  lt2:big;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure solve;
var
  scs,nho,i,t:longint;
  temp:int64;
begin
  d[k][0]:=1; d[k][1]:=1;
  lt2[0]:=1; lt2[1]:=1;
  for i:=k+1 to n do
    begin
      scs:=max(max(d[i-1,0],d[i-k-1,0]),lt2[0]);
      nho:=0; t:=i-k-1;
      for scs:=1 to scs do
        begin
          temp:=d[i-1,scs]<<1-d[t,scs];
          temp+=int64(lt2[scs])+nho;
          if (temp<oo) and (temp>=0) then begin nho:=0; d[i,scs]:=temp; end
          else if temp>=0 then begin nho:=temp div oo; d[i,scs]:=temp mod oo; end
          else begin nho:=-1; d[i,scs]:=temp+oo; end;
        end;
      if nho>0 then
        begin inc(scs); d[i,scs]:=nho; end;
      d[i,0]:=scs;
      scs:=lt2[0]; nho:=0;
      for scs:=1 to scs do
        begin
          lt2[scs]:=lt2[scs]<<1+nho;
          if lt2[scs]<oo then nho:=0 else begin lt2[scs]-=oo; nho:=1; end;
        end;
      if nho>0 then begin inc(lt2[0]); lt2[lt2[0]]:=nho; end;
    end;
end;
procedure ans;
var
  i,ii:longint;
  s:string[10];
begin
  write(f2,d[n,d[n,0]]);
  for i:=d[n,0]-1 downto 1 do
    begin
      str(d[n,i],s);
      for ii:=8-length(s) downto 1 do write(f2,'0');
      write(f2,s);
    end;
  writeln(f2);
end;
begin
  openF;
  read(f1,n,k);
  solve;
  ans;
  closeF;
end.

Download