Это сложная версия задачи. Единственное различие между двумя версиями этой задачи в ограничениях на \(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)
Выходные данные
Выведите \(k+1\) целое число, ответы для каждого \(r\) от \(0\) до \(k\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 3
|
1 49 294 168
|
|
2
|
1 51549919 2
|
1 51549918 0
|