1

every intermediate number in a valid construction is a consecutive block of digits from X
So we start with X and successively take off one digit from either end until you reach a single digit, but ensuring that for each iteration, we pick the construction that gives us the maximum numbers divisible by M.
Consider a contiguous sub-block of X, say X[i…j]. This number must have been formed by adding a digit to a smaller block. There are two possibilities:
- Left Addition: If the leftmost digit X[i] was added last, then before that step the block was X[i+1…j]
- Right Addition: If the rightmost digit X[j] was added last, then before that step the block was X[i…j-1]
The recursive structure is built on these 2 cases
In addition, at the current level we check if the number X[i…j] is divisible by M and count it if it is
We can notice that the optimal solution for X[i…j] depends on the solutions for the two smaller problems: X[i+1…j] and X[i…j-1]
From that, we can conclude that this is a dynamic programming problem

2

C(a,b) := the maximum number of intermediate numbers that are divisible by M when building the part of X that goes from digit a to digit b.
Sub-problem representation:
- Given a list of valid consecutive numbers that grow to form X from a to b, what is the maximum count of numbers divisible by M
If X has n digits, then each unique subproblem is defined by a pair (a, b) where 1 ⇐ a ⇐ b ⇐ n
The total number of distinct sub-problems is given by the number of such pairs: n(n + 1)/2

Given the digit X[a…b]:

if a > b (invalid; could represent the state where there are no digits):
- C(a,b) = 0
if a = b (base case; a single digit):
- C(a,b) = 1 if X[a] % M == 0 else 0
for all a < b (recursive case):
- C(a,b) = max(C(a+1, b), C(a, b-1)) + (X[a…b] % M == 0 ? 1 : 0)