Определим знакочередующуюся сумму массива $$$b$$$ длины $$$k$$$ как $$$\sum_{i = 1}^{k}(-1)^{i+1}b_i$$$.
Вам дан неубывающий$$$^{\text{∗}}$$$ массив $$$a$$$ длины $$$n$$$ такой, что для всех $$$1 \le i \le n,$$$ либо $$$a_i = -1$$$, либо $$$a_i$$$ — целое положительное число. Найдите количество последовательностей $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$, таких, что знакочередующаяся сумма последовательности $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ равна $$$0.$$$ Так как это число может быть большим, выведите его по модулю $$$10^9+7$$$.
Два набора индексов $$$i_1, \ldots, i_{k_1}$$$ и $$$i'_1, \ldots, i'_{k_2}$$$ считаются различными, если $$$k_1 \neq k_2$$$ или существует такой $$$j$$$, что $$$i_j \neq i'_j.$$$
$$$^{\text{∗}}$$$Последовательность $$$a_1, \ldots, a_n$$$ называется неубывающей, если $$$a_1 \le a_2 \le \ldots \le a_n$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано одно целое число $$$n \, (1 \le n \le 2 \cdot 10^5)$$$ — длина массива.
Во второй строке каждого набора входных данных даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива, где $$$\mathbf{a_i = -1}$$$ или $$$\mathbf{1 \leq a_i \leq 10^9}$$$. Гарантируется, что массив неубывающий.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество подпоследовательностей, у которых знакочередующаяся сумма равна нулю по модулю $$$10^9 +7$$$. Подпоследовательность длины $$$0$$$ имеет знакочередующуюся сумму, равную нулю.
45-1 1 1 2 331 2 341 3 5 714-1 -1 -1 1 2 2 3 3 3 5 5 5 5 5
6111536
В первом примере следующие подпоследовательности имеют знакочередующуюся сумму, равную нулю:
| $$$\bullet$$$ | $$$[],$$$ |
| $$$\bullet$$$ | $$$[a_2,a_3] = [1,1]$$$, |
| $$$\bullet$$$ | $$$[a_1, a_2, a_4] = [-1,1,2]$$$, |
| $$$\bullet$$$ | $$$[a_1, a_3, a_4] = [-1,1,2]$$$, |
| $$$\bullet$$$ | $$$[a_1, a_4, a_5] = [-1,2,3]$$$, |
| $$$\bullet$$$ | $$$[a_1,a_2,a_3,a_4,a_5] = [-1,1,1,2,3].$$$ |
Во втором примере только пустая подпоследовательность $$$[]$$$ имеет знакочередующуюся сумму, равную нулю.
| Codeforces Round 1108 (Div. 2) |
|---|
| Закончено |
