SPBINARY - Xâu Nhị Phân

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       611;
  scs           =       21;
  base          =       1000000000;
  lbase         =       9;

type
  big           =       array[0..scs] of longint;

var
  f1,f2         :       text;
  n,maxk        :       longint;
  f             :       array[1..2,1..MAXN,0..1] of big;
  res           :       big;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure add(a,b:big; var c:big); inline;
    var
      i,nho:longint;
    begin
      c[0]:=max(a[0],b[0]);
      nho:=0;
      for i:=1 to c[0] do
        begin
          c[i]:=a[i]+b[i]+nho;
          if c[i]<base then nho:=0
          else begin nho:=1; dec(c[i],base); end;
        end;
      if nho>0 then
        begin
          inc(c[0]);
          c[c[0]]:=nho;
        end;
    end;

procedure print(var a:big); inline;
    var
      i,x,l,j:longint;
    begin
      if a[0]=0 then
        begin
          writeln(f2,0);
          exit;
        end;
      write(f2,a[a[0]]);
      for i:=a[0]-1 downto 1 do
        begin
          l:=0;
          x:=a[i];
          while (x>0) do
            begin
              inc(l);
              x:=x div 10;
            end;
          for j:=1 to lbase-l do write(f2,0);
          write(f2,a[i]);
        end;
    end;

procedure solve;
    var
      i,now,k:longint;
    begin
      now:=1;
      f[1,1,1][0]:=1; f[1,1,1][1]:=1;
      f[1,1,0]:=f[1,1,1];

      for i:=1 to n-1 do
        begin
          fillchar(f[3-now],sizeof(f[3-now]),0);
          for k:=1 to i do
            begin
              if k<maxk then
                begin
                  add(f[now,k,0],f[3-now,k+1,0],f[3-now,k+1,0]);
                  add(f[now,k,1],f[3-now,k+1,1],f[3-now,k+1,1]);
                end;
              add(f[now,k,1],f[3-now,1,0],f[3-now,1,0]);
              add(f[now,k,0],f[3-now,1,1],f[3-now,1,1]);
            end;
          now:=3-now;
        end;

      for i:=1 to maxk do
        begin
          add(res,f[now,i,0],res);
          add(res,f[now,i,1],res);
        end;
      print(res);
    end;

begin
  openF;
  read(f1,n,maxk);
  solve;
  closeF;
end.

Download