SPBINARY - Xâu Nhị Phân

Tác giả: ladpro98

Ngôn ngữ: Pascal

program spbinaryAC;//dp
var     n,k:longint;
        f:array[1..601] of string;

function cong(a,b:string):string;
var     carry,sum,i:longint;
        c:string;
begin
        c:='';
        carry:=0;
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                sum:=ord(a[i])+ord(b[i])-96+carry;
                carry:=sum div 10;
                c:=chr(sum mod 10 + 48) + c;

        end;
        if carry>0 then
        c:=chr(carry+48) +c;
        exit(c);
end;

function tru(a,b:string):string;
var     c:string;
        s,borrow,i:longint;
begin
        borrow:=0;c:='';
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])-ord(b[i])-borrow;
                if s<0 then
                begin
                        s:=s+10;
                        borrow:=1;
                end
                else borrow:=0;
                c:=chr(s+48) +c;
        end;
        while (length(c)>1) and (c[1]='0') do delete(c,1,1);
        exit(c)

end;

procedure dp;
var     i,j:longint;
begin
        f[1]:='2';
        for i:=2 to k-1 do
        begin
                f[i]:=cong(f[i-1],f[i-1]);
        end;
        f[k]:=tru(cong(f[k-1],f[k-1]),'2');
        for i:=k+1 to n do
        begin
                f[i]:=tru(cong(f[i-1],f[i-1]),f[i-k]);
        end;
end;

begin
        readln(n,k);
        inc(k);
        dp;
        write(f[n]);
end.

Download