NKTOSS - Tung đồng xu

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=10000;
      base=1000000000;
      dg=9;
type bignum=array[0..340] of longint;
var n,k:longint;
    re,p:bignum;
    g:array[0..maxn] of bignum;

procedure rf;
begin
     read(n,k);
end;

procedure plus(var a,b:bignum);
var i,mem,max:Longint;
begin
     if b[0]>a[0] then max:=b[0] else max:=a[0];
     mem:=0;
     for i:=1 to max do
     begin
          a[i]:=a[i]+b[i]+mem;
          if a[i]<base then mem:=0
          else
          begin
               mem:=1;
               a[i]:=a[i]-base;
          end;
     end;
     if mem>0 then
     begin
          inc(max);
          a[max]:=1;
     end;
     a[0]:=max;
end;

procedure minus(var a,b,c:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to b[0] do
     begin
          a[i]:=b[i]-c[i]-mem;
          if a[i]>0 then mem:=0
          else
          begin
               a[i]:=a[i]+base;
               mem:=1;
          end;
     end;
     a[0]:=b[0];
     while (a[0]>1) and (a[a[0]]=0) do dec(a[0]);
end;

procedure mul(var a:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to a[0] do
     begin
          a[i]:=a[i] shl 1+mem;
          if a[i]<base then mem:=0
          else
          begin
                mem:=1;
                a[i]:=a[i]-base;
          end;
     end;
     if mem>0 then
     begin
          inc(a[0]);
          a[a[0]]:=1;
     end;
end;

procedure pr;
var i,j:longint;
begin
     p[0]:=1; p[1]:=1;
     g[0,0]:=1; g[0,1]:=1; re[0]:=1;
     for i:=1 to k-1 do
     begin
          mul(p);
          for j:=0 to p[0] do g[i,j]:=p[j];
     end;
     for i:=k to n do
     begin
          mul(p);
          mul(re);
          if i>k then plus(re,g[i-k-1])
          else re[1]:=1;
          if i<=n-k-1 then minus(g[i],p,re);
     end;
end;

procedure wf;
var i,j,l:longint; s:string;
begin
     for i:=re[0] downto 1 do
     begin
          if i<re[0] then
          begin
               str(re[i],s);
               l:=length(s);
               for j:=l+1 to dg do write(0);
          end;
          write(re[i]);
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Download