program kbasednumbers;
  var i:integer;
      a:array[0..16] of longint;
      n,k:word;
begin
 read(n);
 read(k);
 a[0]:=1;
 a[1]:=k-1;
 for i:=2 to n do
   a[i]:=(k-1)*(a[i-1]+a[i-2]);
 writeln(a[n]);
end.

var
  n,k,i               :byte;
  p1,p2,p3            :longint;
begin
  read(n,k);
  p2:=1; p1:=k;
  for i:=1 to n-2 do begin
    p3:=p1;
    p1:=(k-1)*(p1+p2);
    p2:=p3;
  end;
  writeln((k-1)*p1);
end.
Aidin_n7@hotmail.com

i really can't understand the meaning of the problem.
please help me

Let's consider:
f(n, 0) - an amount of valid n digits , k-based number.
f(n, 0) - an amount of valid n digits, k-based number which ends with 0.
f(n, 1) - an amount of valid n digits, k- based number which ends with 1,2,..,k - 1.
We have:
         f(n, 1) = (k - 1)f(n - 1)
         f(n, 0) = f(n - 1, 1) = (k - 1)f(n -2)
So, f(n) = f(n, 1) + f(n, 0) = (k -1)( f(n - 1) + f(n - 2))

Edited by author 20.12.2005 17:39

I get AC
f(t)=f(t-1)*(k-1)+f(t-2)*(k-1);
thanks

It's so simple! And I'm so stupid, that didn't guess it myself. :(