Sos!I really don't know why i always get this reply!Could anybody
point out my fault or give me some testdata?Thanks

> Sos!I really don't know why i always get this reply!Could anybody
> point out my fault or give me some testdata?Thanks
Use DP:
 M[1] = K;
 M[2] = (K-1) * K;

 M[K] = (K-1) * ( Mas[K-2] + Mas[K-1] ); k<N;

 Answer is M[N] = (K-1)*Mas[N-1]

so, A(i)=is the number of valid numbers where the I-th digit is 0
and,B(i)=is the number of valid numbers where the
         I-th digit is IN [1..9]

program timus1009;
const
  maxn=20;
type
  ta=array[0..maxn]of integer;
var
  n,k:integer;
  A,B:ta;
  i:integer;

begin
  while not seekeof do begin
    readln(n);
    readln(k);
    A[1]:=0;
    B[1]:=k-1;
    for i:=2 to n do
    begin
      A[i]:=B[i-1];
      B[i]:=(k-1)*(A[i-1]+B[i-1]);
    end;
    writeln(A[n]+B[n]);
  end;
end.

:)
this is the same thing :)
if you replace A[i-1] = B[i-2] you will get
B[i] = (k - 1) * (B[i - 2] + B[i - 1])