Good Bye 2023 |
---|
Закончено |
Это простая версия задачи. Единственное отличие между двумя версиями этой задачи в ограничениях на $$$k$$$. Вы можете делать взломы только если сданы обе версии задачи.
Вам даны целые числа $$$n$$$, $$$p$$$ и $$$k$$$. Гарантируется, что $$$p$$$ является простым числом.
Для каждого $$$r$$$ от $$$0$$$ до $$$k$$$ найдите количество $$$n \times n$$$ матриц $$$A$$$ над полем$$$^\dagger$$$ целых чисел по модулю $$$p$$$, таких что ранг$$$^\ddagger$$$ матрицы $$$A$$$ в точности равен $$$r$$$. Поскольку эти значения могут быть большими, вам требуется вывести их по модулю $$$998\,244\,353$$$.
$$$^\dagger$$$ https://en.wikipedia.org/wiki/Field_(mathematics)
$$$^\ddagger$$$ https://en.wikipedia.org/wiki/Rank_(linear_algebra)
Первая строка ввода содержит три целых числа $$$n$$$, $$$p$$$ и $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq p < 998\,244\,353$$$, $$$0 \leq k \leq 5000$$$).
Гарантируется, что $$$p$$$ является простым числом.
Выведите $$$k+1$$$ целое число, ответы для каждого $$$r$$$ от $$$0$$$ до $$$k$$$.
3 2 3
1 49 294 168
1 51549919 2
1 51549918 0
Название |
---|