How to solve the specified task?

Consider N-digit numbers in the number system with base K. We will consider the number correct if its K-ary notation does not contain two consecutive zeros.

For example:

  • 1010230 - the correct 7-digit number;
  • 1000198 is not a valid number;
  • 0001235 is not a 7-digit number, but a 4-digit number.

Given the numbers N and K, calculate the number of correct K-ary numbers consisting of N digits.

Limitations: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

enter image description here

  • I will ask the question right away, you only want to solve this one or right away in a normal formulation (there 3 tasks only differ in restrictions). You can try this in the forehead of recursions, as if it were for this solution of the restriction. - pavel
  • This is one task - Vanya Avchyan

1 answer 1

I write immediately the idea of ​​a normal solution (an idea, because I think that the tasks from the thymus should be driven by ourselves). Normal, this means immediately in complete restrictions and not trimmed versions (which, by the way, should lead to this decision).

  1. We don’t need the first digit at all.
  2. By and large, we don’t care what figure, the main thing is 0 or not.

The solution to this problem is to generate a mask of 0 / not 0. (2 ^ 16 variants in the worst case). Further for each mask you need to add 9 ^ to the answer (the number 1 is not a mask). Do not forget that the first element in the mask is always 1.

  1. Suppose we have placed i digits, to place i + 1, we need to know only the value of i digits, the rest of them do not interfere with us.

The solution of a more complicated problem is the dynamics F [i] [d] - the number of ways to make i first digits so that the last digit is d (we remember that only 0 is important to us or not). The recalculation is obvious (from 0 only to 1 and k-1 mode, from 1 to 1 also k-1 and from 1 to 0 1 method). Base F [1] [1] = K-1. O (N) complexity.

Then you can pack all this into a formula, it is not difficult to deduce it, the formula will be reduced to a rapid exponentiation, and the complexity will drop to O (log N).

  • Need a feature or functions - Vanya Avchyan
  • one
    Tasks from the thymus code itself. You have the whole idea, if you ask something incomprehensibly, but rather give your code, I will. - pavel
  • I understand that it is best to study the art of programming yourself. Thank you - Vanya Avchyan