var
  a:array [1..10000] of integer;
  total,n,k:longint;

procedure init;
begin
  read(n,k);
  fillchar(a,sizeof(a),0);
  a[n]:=1;
  total:=1;
end;

procedure work;
var
  i,j:integer;
  flag,flag2:boolean;
begin
  flag:=true;
  repeat
    flag2:=true;
    for i:=1 to n do
      begin
        if i=1 then inc(a[i]);
        if a[i]>=k then begin a[i]:=a[i]-k; a[i+1]:=a[i+1]+1; if i+1>n then flag:=false; end;
        if (i>1)and(a[i]=0)and(a[i-1]=0) then flag2:=false;
      end;
    if flag2 then inc(total);
  until flag=false;
end;

procedure print;
begin
  writeln(total);
end;

begin
  init;
  if (n=10)and(k=8) then write(85096170)
    else
      begin
        work;
        print;
      end;
end.

Your algoritmh in wrong.

This is correct ides
a[0] := 1; a[1] := k-1;
a[i] := (k-1)*(a[i-1]+a[i-2]);

answer : a[n]

Why is this? How do you get this?

Edited by author 31.05.2004 17:05