Думаю, решать эту задачу примерно так:
Допустим,
M = AAAA BBBB
N = CCCC DDDD
1. Считаем массив сумм, который в исходном решении обозначен за C.
2. Считаем кол-во счастливых билетов от AAAA BBBB до AAAA 9999.
3. Считаем кол-во счастливых билетов от (AAAA+1) 0000 до (СССС-1) 9999 - то есть, массив сумм от AAAA+1 до CCCC-1 и поэлементно умножаем его на массив C из первого шага, получив в конечном итоге сумму.
4. Считаем кол-во счастливых билетов от CCCC 0000 до CCCC DDDD.
5. Суммируем все три количества на шагах 2-4, и задача решена.
Сложность каждой подзадачи такая же, как у исходной задачи. Думаю, понятно набросал алгоритм.
UPD: Ну и крайний случай учесть, если первые 4 цифры M и N совпадают - тогда всё это не надо считать, а провести только 1 перебор от правых 4 цифр первого числа до правых четырёх второго, и проверить их сумму цифр на равенство левой сумме цифр.