2246C.md (2353B)
1 Source: https://codeforces.com/problemset/problem/2246/C 2 3 C. 0mar and Alternating Sums 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Define the alternating sum of an array $b$ of length $k$ to be $\sum_{i = 1}^{k}(-1)^{i+1}b_i$. 22 23 You are given a non-decreasing$^{\text{∗}}$ array $a$ of length $n$ such that for all $1 \le i \le n,$ either $a_i = -1$ or $a_i$ is a positive integer. Find the number of sequences $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that the alternating sum of the sequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ is $0.$ Since this number may be large, output it modulo $10^9+7$. 24 25 Two sets $i_1, \ldots, i_{k_1}$ and $i'_1, \ldots, i'_{k_2}$ of indices are considered different if $k_1 \neq k_2$ or there exists a $j$ such that $i_j \neq i'_j.$ 26 27 $^{\text{∗}}$A sequence $a_1, \ldots, a_n$ is non-decreasing if $a_1 \le a_2 \le \ldots \le a_n$. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n \, (1 \le n \le 2 \cdot 10^5)$ — the length of the array. 34 35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ — the elements of the array where $\mathbf{a_i = -1}$ or $\mathbf{1 \leq a_i \leq 10^9}$. It is guaranteed that the array is non-decreasing. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each testcase, output a single integer — the number of subsequences that have an alternating sum of zero modulo $10^9 +7$. A subsequence of length $0$ is considered to have an alternating sum of zero. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 5 51 52 -1 1 1 2 3 53 54 3 55 56 1 2 3 57 58 4 59 60 1 3 5 7 61 62 14 63 64 -1 -1 -1 1 2 2 3 3 3 5 5 5 5 5 65 ``` 66 67 Output 68 69 ``` 70 6 71 72 1 73 74 1 75 76 1536 77 ``` 78 79 Note 80 81 In the first example, the following subsequences have an alternating sum of zero: 82 83 | | | 84 | --- | --- | 85 | $\bullet$ | $[],$ | 86 | $\bullet$ | $[a_2,a_3] = [1,1]$, | 87 | $\bullet$ | $[a_1, a_2, a_4] = [-1,1,2]$, | 88 | $\bullet$ | $[a_1, a_3, a_4] = [-1,1,2]$, | 89 | $\bullet$ | $[a_1, a_4, a_5] = [-1,2,3]$, | 90 | $\bullet$ | $[a_1,a_2,a_3,a_4,a_5] = [-1,1,1,2,3].$ | 91 92 In the second example, only the empty subsequence $[]$ has an alternating sum of zero.