N-факториал

$$$N$$$-факториалы растут очень быстро. Так, $$$5$$$-факториал это $$$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4 \cdot 5^5 = 86400000$$$, а $$$6$$$-факториал превышает $$$10^{12}$$$. Так как сумма, заданная в задаче, ограничена числом $$$10^9$$$, то ее слагаемыми могут быть только $$$N$$$-факториалы для $$$N \le 5$$$. Предподсчитаем все их значения.

Затем, также предподсчитаем все возможные суммы, которые могут получиться при сложении двух $$$N$$$-факториалов, за $$$O(N^2)$$$, и сохраним их в массиве.

Далее, получая чиcло на вход, нам остается лишь проверять, присутствует ли оно в нашем массиве. Это можно сделать при помощи бинарного или простого линейного поиска.