n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).
3. else answer(n) = ( k-1 ) * ( answer(n-1,k) + answer(n-2,k) ).

Edited by author 20.06.2010 04:04

是好啊！！！！

n>=2 !!!

There is good O(1) memory and O(n) algo (n - number length)
info: http://skydos.blogspot.com/2010/07/k.html

Okay, I'll join to Captains Obvious. You can find an answer with O(1) memory and O(logN) time.

Can you explain this algo?
Really interesting to know better one.
Thx.

Sure, you're welcome.
Okay, we're already know, that the answer can be found reccurently: F(N) = (K-1)*(F(K-1)+F(N-2)), where F(0) = 1, F(1) = K-1. We see, that the {F(N)} sequence is very similar to Fibonacci's one and can assume some facts. I see two different approaches to solve the problem.

1) First way is to build characteristic equation, solve it and get an exact formula for F(N). I didn't try this way, because I foresaw some problems with precision and float calculations. If you're interested, you can turn to this article as a manual:
http://www.intuit.ru/department/algorithms/algocombi/8/2.html

2) I assumed, that method with fast matrix exponentiation will work as well as for Fibonacci's numbers.
Just consider a matrix: L(N) = {{F(N+1), F(N)}, {F(N), F(N-1)}}.
Let's try to find such R, that L(N)*R = L(N+1).
If you write down this information, you'll easily see, that R = {{K-1, 1}, {K-1, 0}}. So all you need is to find L(1)*R.pow(N-2).

Hope this information was helpful, I'm not sure it is the best way to describe an approach though. :-)

Edited by author 16.08.2010 13:34

Actually, I implemented only O(N)-solution before. Today I wrote a code for a fast exponentiation, but (it seems I don't know java well) my time increased in #1013, where BigInteger is needed. Strange. :-)

Artem Khizha [DNU]
Thx for explanations and idea! I got it!
Really nice approach with matrixes!

#include <iostream>

using namespace std;
unsigned long stepen(unsigned long K,unsigned long N)
{
    unsigned long i, result=1;
    if (N<0)
        return 0;
    else
    {
        i=1;
        for(; i<=N; i++)
            result*=K;
        return result;
    }
}

int main()
{
    unsigned long N, K, i, result;
    cin>>N;
    cin>>K;


        result=stepen(K, N)-(stepen(K,N-2)+stepen(K, N-1)-1);
        cout<<result<<endl;
        //system("Pause");
        return 0;

}

WA #2. Why?

good job!

>>dima11221122

Firstly, I came up with something like that and got WA2 too.

N = (k-1)^n + n(k-1)^(n-1) - that formula looks pretty alright; but it isn't.
It assumes there can't be more than one zero in the number, while there obviously can. The actual answer is something like that -
N = (k-1)^n + n * (П(i=1 to min(k,n)) of (k-i)^(n-1))
and i think it's anyways easier to solve that like original poster did.

Btw, your code is sooooo bad; u might wanna do something about that.

Edited by author 26.11.2011 06:42

Thanks! Good algo

I am not sure, how the number of zero digit numbers (of course, without two zeros in it) become 1.

Edited by author 29.03.2012 02:38

Can anybody tell me where can i get some info about this topic(k-based numbers), I really don't get from where cames this recurrent formula? Greetings

How can we get valid n-digit number? Trivially, we can append each of (k-1) possible digits (k digits except for 0) to the front of each of (n-1)-digit valid numbers.
But we can also form valid number this way: append 0 to the front of (n-2)-digit valid number, and then append (k-1) possible digits, as in the first case.

This gives us F(n) = (k-1)*F(n-1)+(k-1)*F(n-2), where F is the function to yield the amount of valid n-digit numbers.

I'd recommend you to ensure this yields only the valid numbers, think why can't it produce duplicates, and whether other means to construct valid numbers are possible.

Then you follow Artem Khizha's [DNU] recipe and get an AC (=

Edited by author 08.08.2012 19:05

HI David,
   The problem statement language is confusing.   A "k-based number" is a number represented in base "k", that's all.

>  Amir Aupov [MIPT]

 I like your explanation.   I approached the construction of N digit numbers from N-1 digit numbers in the typical way of constructing numbers: multiply N-1 digit number by base, and add in the new digits to the units position.    This has the benefit of being clear and natural, so we can be sure that we're not missing any numbers.   It has the disadvantage that you must track numbers that end in zero separately from those that don't.   But this is still quite simple:
Z(n): # of valid numbers ending in zero
NZ(n): # of valid numbers not ending in zero
Z(2) = k - 1
NZ(2) = (k - 1) * k - (k - 1)   (total number of valid 2-digit numbers, minus those that end in 0)
then,
Z(n) = NZ(n - 1)
NZ(n) = (Z(n-1) + NZ(n-1)) * (k - 1)

Compute Z(n) and NZ(n) iteratively (DP), and then output F(n) at the end
F(n) = Z(n) + NZ(n)