Pinely Round 3 (Div. 1 + Div. 2) |
---|
Закончено |
В простой версии задачи $$$a_i$$$ находятся в диапазоне $$$[0, n]$$$; в сложной версии $$$a_i$$$ находятся в диапазоне $$$[-1, n]$$$ и определение хорошей перестановки немного отличается. Вы можете делать взломы, только если обе версии задачи решены.
Вам дано целое число $$$n$$$ и массив $$$a_1, a_2, \dots, a_n$$$ целых чисел в диапазоне $$$[-1, n]$$$.
Перестановка $$$p_1, p_2, \dots, p_n$$$ в $$$[1, 2, \dots, n]$$$ называется хорошей, если для каждого $$$i$$$ верно следующее утверждение:
Посчитайте количество хороших перестановок $$$[1, 2, \dots, n]$$$ по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le n$$$), которые описывают критерии хорошей перестановки.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одну строку, содержащую количество хороших перестановок по модулю $$$998\,244\,353$$$.
105-1 -1 -1 -1 -151 2 3 4 560 2 2 2 -1 -16-1 -1 -1 -1 -1 56-1 -1 3 2 -1 -1150 0 -1 -1 -1 2 2 -1 -1 -1 -1 9 11 13 1560 2 2 2 4 660 1 3 4 5 561 2 3 2 4 6150 0 1 1 1 2 3 4 5 6 7 9 11 13 15
120 1 4 0 0 494403526 4 0 0 532305727
В первом наборе входных данных все перестановки длины $$$5$$$ являются хорошими, поэтому существует $$$120$$$ хороших перестановок.
Во втором наборе входных данных единственной хорошей перестановкой является $$$[1, 2, 3, 4, 5]$$$.
В третьем наборе входных данных существует $$$4$$$ хороших перестановки: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. Например, $$$[2, 1, 5, 6, 3, 4]$$$ — хорошая, потому что:
Название |
---|