Автор задачи: Орешников Даниил, разработчик: Николай Будин
В этой задаче есть два случая.
Если $$$\frac{n}{2}$$$ — четное. Тогда обозначим за $$$a$$$ сумму цифр на нечетных позициях в первой половине числа. За $$$b$$$ обозначим сумму цифр на четных позициях в первой половине числа. За $$$c$$$ – на нечетных позициях во второй половине. За $$$d$$$ — на четных позициях во второй половине. Мы знаем, что $$$a + b = c + d$$$ и $$$a + c = b + d$$$. Преобразованиями можно получить, что $$$b = c$$$ и $$$a = d$$$. Заметим, что эти равенства необходимые и достаточные для того, чтобы билетик был супер-счастливым.
Обозначим за $$$f(l, s)$$$ количество последовательностей из $$$l$$$ цифр с суммой $$$s$$$. Тогда ответом является:
$$$$$$\sum\limits_{a, b} f^2(\frac{n}{4}, a) \cdot f^2(\frac{n}{4}, b) = (\sum\limits_{a} f^2(\frac{n}{4}, a))^2$$$$$$
Значит, нужно научиться вычислять значения $$$f(\frac{n}{4}, a)$$$ ($$$0 \le a \le 10 \cdot \frac{n}{4}$$$). Для этого можно воспользоваться быстрым преобразованием Фурье для перемножения многочленов и вычислить:
$$$$$$(1 + x + \dots + x^8 + x^9)^{l}$$$$$$
Тогда коэффициент при $$$x^s$$$ будет равняться количеству способов выбрать последовательность из $$$l$$$ цифр так, чтобы их сумма равнялась $$$s$$$.
Если же $$$\frac{n}{2}$$$ нечетно, то по аналогичным соображениям ответ равняется:
$$$$$$(\sum\limits_{a} f^2(\lfloor\frac{n}{4}\rfloor, a)) \cdot (\sum\limits_{a} f^2(\lceil\frac{n}{4}\rceil, a))$$$$$$