i use the algorithm above.
let x1[n] be the number that the frist digit was 0 in k-
based and length is n.
let x2[n] be the number that the frist digit was none-0 in
k-based and length is n.

then we can get the formula:
    x1[n]=x2[n-1];
    x2[n]=(x1[n-1]+x2[n-1])*(k-1)

the answer will be stored at x2[n]
i think it is correct, but why i get the wrong answer?

I think the correct answer must be the sum of x1[n] and x2[n]

> i use the algorithm above.
> let x1[n] be the number that the frist digit was 0 in k-
> based and length is n.
> let x2[n] be the number that the frist digit was none-0 in
> k-based and length is n.
>
> then we can get the formula:
>     x1[n]=x2[n-1];
>     x2[n]=(x1[n-1]+x2[n-1])*(k-1)
>
> the answer will be stored at x2[n]
> i think it is correct, but why i get the wrong answer?
>

> I think the correct answer must be the sum of x1[n] and x2
[n]
>
> > i use the algorithm above.
> > let x1[n] be the number that the frist digit was 0 in k-
> > based and length is n.
> > let x2[n] be the number that the frist digit was none-0
in
> > k-based and length is n.
> >
i found my mistakes...
the algorithm is correct..
just because there is a bug in my output.
> > then we can get the formula:
> >     x1[n]=x2[n-1];
> >     x2[n]=(x1[n-1]+x2[n-1])*(k-1)
> >
> > the answer will be stored at x2[n]
> > i think it is correct, but why i get the wrong answer?
> >

Let's assume two functions F(N) and G(N).
F(N) is a sum of N-digits K-base numbers
(notice : here, the first digit can be 0)
G(N) is a sum of N-digits K-base numbers
(here, the first digit can't be 0)
so we want to get G(N).

G(N)=(k-1)*F(N-1)
F(N)=(k-1)*(F(n-1)+F(N-2))

And pay attention to N=1 and N=2, the answer is
special.

> Let's assume two functions F(N) and G(N).
> F(N) is a sum of N-digits K-base numbers
> (notice : here, the first digit can be 0)
> G(N) is a sum of N-digits K-base numbers
> (here, the first digit can't be 0)
> so we want to get G(N).
>
> G(N)=(k-1)*F(N-1)
> F(N)=(k-1)*(F(n-1)+F(N-2))
but N must be >=2
so...G[1] couldn't be printed...

and there is one thing that you misunderstood...
the first digit of F(N) must be '0'.
the first digit is the left most one.
and the formula was worng...

the correct one is as follow:
F(N)=G(N-1)
G(N)=(k-1)*(G(N-1)+F(N-1))

and I use the formula to solve the problem...
> And pay attention to N=1 and N=2, the answer is
> special.
>
>

But I have passed :)
And I mean that N=1 and N=2 you must solve it specially.
F(1)=K
F(2)=K*K-1
That's all right.

> But I have passed :)
> And I mean that N=1 and N=2 you must solve it specially.
> F(1)=K
> F(2)=K*K-1
> That's all right.
well, anyway i learn another way of solution...:)

:)
Anyway I learn another way of solution too :P