Задача №113774. Фурье?
Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.
Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .
Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 3 + 2 3 + 1 3 = 27 + 8 + 1 = 36 .
Поскольку задача должна быть интересной, вам нужно посчитать интересность всех чисел от 1 до n по модулю MOD .
В единственной строке входных данных задаются два числа n и MOD ( 1 ≤ n ≤ 10 5 , 1 ≤ MOD ≤ 10 9 + 7 ) — максимальное число, для которого надо посчитать интересность, и модуль.
Модуль не обязательно простой.
Выведите n строк, в i -й строке должна содержаться интересность числа i по модулю MOD .
Данная задача содержит 8 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.
- 1 ≤ n ≤ 5 , 5 баллов.
- 1 ≤ n ≤ 10 , 5 баллов.
- 1 ≤ n ≤ 20 , 10 баллов.
- 1 ≤ n ≤ 100 , 10 баллов.
- 1 ≤ n ≤ 1000 , 10 баллов.
- 1 ≤ n ≤ 5000 , 10 баллов.
- 1 ≤ n ≤ 50 000 , 25 баллов.
- 1 ≤ n ≤ 100 000 , 25 баллов.
3 998244353
1 9 36
10 3
1 0 0 0 2 2 0 2 2 0