Birthday Gift

Boiling it down, this problem asks us to count the number of 'a' digit numbers which are equal to 'b' mod 225.

We first notice that 'a' is 10^18, so far too large to do any math on or even iterate through. We also notice that 225 is an oddly specific number, and factoring, we find that it is 25 * 9, both factors of which have straightforward divisibility checks, whereby x % 25 = 0 is demonstrated by the last two digits being 00, 25, 50, or 75, and x % 9 = 0 demonstrated by the sum of the digits being divisible by 9. We can determine divisibility by 225 by checking if a number holds both of these properties.

In order to uncomplicate things, we will first consider a case where b = 0, and then see if we can extend.

Easy Solution

Let us consider building up the number starting from the last 2 digits. We could create a 3-d DP considering

1. The value of the last digit added
2. the sum of the digits added mod 9
3. How many total digits in the number

Then our recurrence relation involves appending each digit which is not the same as the previous digit, and incrementing that new value/digit combo by the current value. We can seed the array with 2 digits, 25, 50, and 75, and their sums. We then iterate to 'a' digits. This would yield a correct solution, however, at 10^18 for the digit count is much too high to be feasible.

We can notice, however, that we can actually generate a transformation matrix, as the "steps" we take to compute each stage from the last are identical. Consider defining the DP array as 1-dimensional, encoding the last digit and current sum as a single index:

(last digit, sum)

0,0	0,1	0,2	...	9,9
count summing 0, ending with 0	count summing 0, ending with 1	count summing 0, ending with 2	...	count summing 9, ending with 9

We can then compute the transformation T:

(0,0) = (0,1) + (0,2) + (0,3) + (0,4) + ... + (0,9)  # If we end with a 0, the value didn't change, so the previous sum was 0 in all cases. Note that we cannot include (0,0), since that would give us two 0's in a row
(1,0) = (1,1) + (1,2) ... + (1,9) # Same as above. if we end with a 0, the sum doesn't change
...
(0,1) = (9,0) + (9,2) + (9,3) + ... + (9,9) # The previous sum must be 9, since we added 1, and ended up at 0. We also can't include (9,1) as that would lead to duplicate 1's
(1,1) = (0,0) + (1,2) + (1,3) + ... + (1,9)
...
(9,9) = (0,0) + (0,1) + (0,2) + ... + (0,8)

The initial state A is comprised of the following:

(7,2) = 1 # 25, 2 + 5 = 7, last number is "2"
(5,0) = 1 # 50
(2,7) = 1 # 75

We can then apply the transformation:

A_1 = AT

and iteratively, a-2 times (since we started with 2 digits, we only need a-2 applications of the transformation)

A_a-2 = AT^(a-2)

Now, we obviously cannot perform this multiplication 'a-2' times, but we can, however, use fast exponentiation, which arrives at T^(a-2) in log time, using the following:

T^x = T^(x/2) * T(x/2) if x is even T^x = T * T^(x-1) if x is odd.

As T is a 100x100 matrix, that's 1,000,000 multiplications per matrix-multiply, which we'll do about 60 times. 60 million should be fast enough to get us to A_a-2. Once we have computed this, we simply sum the values with a leading digit other than 0 whose sum is 0.

Making it work for b != 0

Changing b is not prohibitive. It just means that our starting 3 or 4 2 digit elements increase such that initial_elements%25 = b%25, and our checking of the sum of the digits must be such that sum%9 = b%9. This works as a rather degernerate case of the chinese remainder theorem, as 9 and 25 are coprime.