ac1066.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1066;
const
  maxn=200;
  maxl=30;
  base=100000000;
type
  bignum=array[-1..6]of longint;
var
  fib:array[1..10]of string[55];
  joint:array[boolean{odd(index)}]of string[maxl*2-2];
  ans:array[0..2{index mod 3}]of bignum;
  s:string[maxl];
  n,i,l:word;
function match(t:string):byte;
  var
    i:byte;
  begin
    match:=0;
    for i:=1 to length(t)-l+1 do
      if copy(t,i,l)=s then inc(match);
  end;
procedure sum(m:byte);
  var
    i:byte;
  begin
    ans[m,-1]:=ans[(m+2) mod 3,-1];
    for i:=0 to ans[m,-1] do begin
      ans[m,i]:=ans[0,i]+ans[1,i]+ans[2,i];
      inc(ans[m,i+1],ans[m,i] div base);
      ans[m,i]:=ans[m,i] mod base;
    end;
    if ans[m,ans[m,-1]+1]>0 then inc(ans[m,-1]);
  end;
procedure out(a:bignum);
  var
    i:shortint;
    s:string[8];
  begin
    write(a[a[-1]]);
    for i:=a[-1]-1 downto 0 do begin
      str(a[i],s);
      while length(s)<8 do s:='0'+s;
      write(s);
    end;
    writeln;
  end;
begin
  fib[1]:='b';fib[2]:='a';
  for i:=3 to 10 do
    fib[i]:=fib[i-1]+fib[i-2];
  joint[false]:=copy(fib[9],6,maxl-1)+copy(fib[9],1,maxl-1);
  joint[true]:=copy(fib[10],27,maxl-1)+copy(fib[9],1,maxl-1);

  repeat
    readln(s);readln(n);l:=length(s);
    if n<11 then
      writeln(match(fib[n]))
    else begin
      fillchar(ans,sizeof(ans),0);
      ans[0{9},0]:=match(fib[9]);ans[1{10},0]:=match(fib[10]);
      for i:=11 to n do begin
        fillchar(ans[i mod 3],sizeof(ans[i mod 3]),0);
        ans[i mod 3,0]:=match(copy(joint[odd(i)],maxl+1-l,l*2-2));
        sum(i mod 3);
      end;
      out(ans[n mod 3]);
    end;
  until seekeof;
end.