please i don't understaind .

a[0]=1;
a[1]=(k-1);
a[i]=(k-1)*(a[i-1]+a[i-2]);

for n=2 and k = 10 the answer is 90 allright,but ,from my point of view for n=2 and k = 9 the right answer is 99 ,2 digits number 9 based, but the algo show 72 , I've AC but, is this the right algo?.

sorry but my english is too bad .

a[2] = k*k-k
This is all numbers from 10 to 88 (if k = 9 and n = 2)

not all, the number 19, 29, 39, 49 .. 79 is not allowed !

FireHeart: you don't have the digit '9' when k=9

 that is a CLASSICAL math problem , i didnt realize it till i got 6 WAs. we fix the first number to be nonzero,and let
f(n) be all the correct numbers . suppose the second digit is not zero ,we have f(n-1) correct ways. otherwise,we have f(n-2) ways. by addition law ,we have
f(n)=(k-1)(f(n-1)+f(n-2)) . the idea is very classical and we should remember it all the time .

It is a classical combinatorial problem. You can solve it with the elegant recurrent relation, but figuring it out how to do it yourself is more valuable. I did it using some combinatoric (i.e.: the number we seek is sum of the K-based numbers with N digits who have exactly X zeroes (i.e. K-X free digits from 1..K-1) and don't have adjacent zeroes (sometimes this is zero, when X > N-X). If f(N,K,X) is this number, we seek sum(X=0 to N-1) f(N,K,X) (we can lower the upper bound X-1 but there's no need if you compute f properly)

Edited by author 22.07.2008 15:30