Чуть более суток назад появился пост, с ужасно оформленным вопросом о казалось бы простой задаче. Пост был заминусован, но я попытался решить задачу, и не смог этого сделать
Условие в человеческом виде выглядит примерно так:
На входе дано число n <= 200. Предположим мы выписали все n*2 значные номера(с ведущими нулями) счастливых билетов. Билет считается счастливым, если сумма первых n цифр равна сумме последних n цифр. В выходной файл нужно вывести 10 чисел — сколько раз мы написали цифру 0, цифру 1, и т.д.

В голове вроде сразу появилось ДП, но оно оказалось медленным, я уже по-разному его попереписывал, но все равно получется слишком медленно для указаных ограничений.
Может кто-нибудь из 43 человек заминусовавших автора знает как решать эту задачу?

Вот мой код

Основные тормоза здесь в строках 63-67. Может можно здесь применить быстрое умножение? Хотя для массива в 200 элементов имхо это не даст сильного ускорения, может можно придумать простую свёртку, чтобы считать это дело? Нам ведь не нужен сам результат умножения, нам нужна сумма a[i] * i, где a это многочлен dcnt в квадрате. Сейчас код работает 13 секунд, но комп у меня довольно мощный, и это многовато. Асимптотика выходит B^2 * N^3 B = 10 (основание СС).
UPD: забыл указать, что ответ нужно вывести по модулю 10^9 + 7