Гости по юртам


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На джайлоо Сон-Куль приехали n туристов, и для них поставили юрты. Все юрты одинаковые, а туристы различаются. Хозяйка Жылдыз хочет знать, сколькими способами можно расселить туристов ровно в k юрт так, чтобы ни одна юрта не пустовала. Два способа различаются, если в одном из них два туриста живут в одной юрте, а в другом — в разных (юрты между собой не различаются).

Рисунок

Хозяйка ещё не знает, сколько юрт поставят, поэтому просит ответ сразу для всех k = 1, 2, …, K. Ответы выведите по модулю 998244353.

Входные данные

В единственной строке — два целых числа n и K (1 ≤ n ≤ 10¹⁸, 1 ≤ K ≤ 2 · 10⁵).

Выходные данные

Выведите K чисел через пробел: количество способов для k = 1, …, K по модулю 998244353.

Пример 1

Вход:

4 5

Выход:

1 7 6 1 0

Пояснение

Четырёх туристов в одну юрту можно поселить одним способом, в две — семью (3 + 1 четырьмя способами и 2 + 2 тремя), в три — шестью (выбираем пару, которая живёт вместе), в четыре — одним. В пять юрт четырёх туристов не расселить.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, K ≤ 40, ещё в 5 % тестов n, K ≤ 1000.

Подсказка

Это числа Стирлинга второго рода. По формуле включений-исключений k! · S(n, k) = Σ_{j=0}^{k} (−1)^(k−j) C(k, j) j^n, а это свёртка двух последовательностей.


Комментарии

Еще нет ни одного комментария.