Hello 2024 |
---|
Закончено |
Есть неизвестный массив $$$a$$$ длины $$$n$$$, состоящий только из $$$1$$$ и $$$-1$$$. Пусть $$$p$$$ — массив префиксных сумм массива $$$a$$$. Более формально, $$$p$$$ — это массив длины $$$n$$$, в котором $$$p_i = a_1 + a_2 + \ldots + a_i$$$. После этого массив $$$p$$$ сортируется в неубывающем порядке. Например, если $$$a = [1, -1, -1, 1, 1]$$$, то $$$p = [1, 0, -1, 0, 1]$$$ до сортировки и $$$p = [-1, 0, 0, 1, 1]$$$ после сортировки.
Вам дан массив префиксных сумм $$$p$$$ после сортировки, но вы не знаете, чему был равен массив $$$a$$$. Ваша задача — посчитать количество исходных массивов $$$a$$$, для которых в результате сортировки массива префиксных сумм получается заданный массив $$$p$$$. Поскольку это число может быть большим, от вас требуется только найти его по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину неизвестного массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$|p_i| \le n$$$) — $$$n$$$ префиксных сумм массива $$$a$$$, отсортированных в порядке неубывания.
Гарантируется, что $$$p_1 \le p_2 \le \ldots \le p_n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Для каждого набора входных данных выведите ответ по модулю $$$998\,244\,353$$$.
510113-1 1 25-1 0 0 1 15-4 -3 -3 -2 -1
0 1 0 3 1
В первых двух наборах входных данных единственными возможными массивами $$$a$$$ для $$$n = 1$$$ являются $$$a = [1]$$$ и $$$a = [-1]$$$. Соответствующие им отсортированные массивы префиксных сумм $$$p$$$ — $$$p = [1]$$$ и $$$p = [-1]$$$. Следовательно, не существует массива $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [0]$$$. Но существует ровно $$$1$$$ массив $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [1]$$$.
В третьем наборе входных данных можно доказать, что не существует массива $$$a$$$, который мог бы привести к отсортированному массиву префиксных сумм $$$p = [-1, 1, 2]$$$.
В четвертом наборе входных данных существует $$$3$$$ возможных массива $$$a$$$, которые могут привести к отсортированному массиву префиксных сумм $$$p = [-1, 0, 0, 1, 1]$$$.
Для пятого набора входных данных единственным возможным массивом $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [-4, -3, -3, -2, -1]$$$, является $$$a = [-1, -1, -1, -1, 1]$$$.
Название |
---|