think-cell Round 1 |
---|
Закончено |
У Стека есть массив $$$a$$$ длины $$$n$$$ такой, что $$$a_i = i$$$ для всех $$$i$$$ ($$$1 \leq i \leq n$$$). Он выберет целое положительное число $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) и выполнит следующую операцию над $$$a$$$ любое число раз (возможно, $$$0$$$):
Стеку стало интересно, сколько массивов $$$a$$$ он может получить в итоге для каждого $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$). Поскольку Стек плохо справляется с математическими задачами, ему нужна ваша помощь.
Поскольку количество массивов может быть слишком большим, выведите его по модулю $$$998\,244\,353$$$.
$$$^\dagger$$$ Последовательность $$$x$$$ является подпоследовательностью $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов. Например, $$$[1, 3]$$$, $$$[1, 2, 3]$$$ и $$$[2, 3]$$$ являются подпоследовательностями $$$[1, 2, 3]$$$. С другой стороны, $$$[3, 1]$$$ и $$$[2, 1, 3]$$$ не являются подпоследовательностями $$$[1, 2, 3]$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — длину массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных в отдельной строке выведите $$$\lfloor \frac{n-1}{2} \rfloor$$$ целых чисел, разделенных пробелами, где $$$i$$$-е число равняется количеству (по модулю $$$998\,244\,353$$$) массивов, которые Стек может получить, если выберет $$$k=i$$$.
434510
2 4 10 2 487 162 85 10
В первом наборе входных данных для $$$k=1$$$ возможны два $$$a$$$:
Во втором наборе входных данных для $$$k=1$$$ возможны четыре $$$a$$$:
В третьем наборе входных данных для $$$k=2$$$ возможны два $$$a$$$:
Название |
---|