We need to solve this task using dynamic programming because the brute force will give TLE. So how do we do it? Let us handle the case of N=1 separately, it is obvious that the answer for N=1 will be K. So for the rest, Suppose we have the numbers of length I of the base J. So how many number can we form with the base J and length I+1. The length increased by 1 which means that we need to add one more digit ( digits from 0 ,1,2,...K-1) to the numbers of length I and base J which satisfies the problem demand. So, if the number ended with 0 we can add (K-1) digits from 1 to (K-1) and if the last digit is not 0 than we can add every digit form 0 to K-1. We need to keep an array of pairs A[I][J] where A[I][J]->first shows the number of numbers on length I of base J which end in a non zero digit and A[I][J]->second shows the number of numbers of length I of base J which end with the digit 0. ==>> A[I][J]->second=A[I-1][J]->first and A[I][J]->first=(A[I-1][J]->first+A[I-1][J]->second)*(i-1).
No comments:
Post a Comment