Codeforces Global Round 26 |
---|
Закончено |
Две версии этой задачи отличаются друг от друга. Возможно, вы захотите прочитать обе версии. Вы сможете делать взломы, только если обе версии решены.
Вам дан массив $$$a$$$ длины $$$n$$$. Изначально $$$c = 0$$$. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ (в порядке возрастания) выполните ровно одно из следующих действий:
Пусть максимальное возможное конечное значение $$$c$$$ после описанной выше процедуры равно $$$k$$$. Найдите количество уникальных процедур, в результате которых получается $$$c = k$$$. Две процедуры различны, если при каком-либо индексе $$$i$$$ одна процедура выбрала вариант $$$1$$$, а другая — вариант $$$2$$$, даже если после этого хода значение $$$c$$$ для обеих процедур одинаково.
Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).
Вторая строка каждого случая содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество уникальных процедур, в результате которых получается $$$c = k$$$, по модулю $$$998\,244\,353$$$.
542 -5 3 -381 4 3 4 1 4 3 43-1 -2 -34-1000000000 1000000000 1000000000 100000000041 9 8 4
12 256 1 8 16
В первом наборе входных данных можно показать, что максимальное конечное значение $$$c$$$ равно $$$3$$$. Существует $$$12$$$ способов достичь этого, потому что для получения $$$3$$$ мы должны взять абсолютное значение при индексах $$$2$$$ или $$$4$$$, или при обоих, что дает $$$3$$$ способа. Для двух других индексов значение не меняется от того, берем мы абсолютное значение или нет, поэтому для них у нас есть $$$2 \cdot 2 = 4$$$ способа. Итого, у нас есть $$$3 \cdot 4 = 12$$$ способов.
Во втором наборе входных данных взятие абсолютного значения ничего не изменит, поэтому мы можем либо брать абсолютное значение, либо нет, для каждого индекса. Это дает нам $$$2^8 = 256$$$ возможных способов.
Название |
---|