2155C.md (2927B)
1 Source: https://codeforces.com/problemset/problem/2155/C 2 3 C. The Ancient Wizards' Capes 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 There are $n$ wizards in a row numbered $1$ to $n$ from left to right. Each wizard has an invisibility cape which can be worn either on his left side or on his right side. Harry walks from the position of wizard $1$ until the position of wizard $n$ ($1 \le n \le 10^5$), and registers how many wizards he sees from each wizard's position. A wizard in position $j$ is visible from position $i$ if: 22 23 * Wizard $j$ wears his cape on his left side and $i \ge j$. 24 * Wizard $j$ wears his cape on his right side and $i \le j$. 25 26 In particular, note that wizard $i$ is visible from position $i$. 27 28 Harry's list is very old but, after much work, you managed to decipher it. The list is an array $a$ of $n$ elements, where the $i$-th element $a_i$ ($1 \le a_i \le n$) is the number of wizards that Harry saw from the position of wizard $i$. 29 30 Your task is to determine how many of all the possible cape arrangements that Harry could have seen are consistent with the data recorded by the list, modulo $676\,767\,677$. 31 32 Input 33 34 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. 35 36 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of $a$. 37 38 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$. 39 40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 41 42 Output 43 44 For each test case, print one integer — the number of arrangements for the wizards' capes that satisfy the condition, modulo $676\,767\,677$. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 1 54 55 1 56 57 4 58 59 4 4 3 2 60 61 3 62 63 1 3 2 64 65 2 66 67 2 1 68 69 3 70 71 2 2 2 72 73 3 74 75 3 2 3 76 77 3 78 79 3 2 2 80 ``` 81 82 Output 83 84 ``` 85 2 86 87 1 88 89 0 90 91 1 92 93 2 94 95 0 96 97 0 98 ``` 99 100 Note 101 102 The image below shows an arrangement of capes that matches Harry's list in the second test case. 103 104  105 106 Wizard 1 has the invisibility cape on his left side, while wizards $2$, $3$, and $4$ wear it on their right side. 107 108 * From position $1$, we can see wizards $1$, $2$, $3$, and $4$. 109 * From position $2$, we can see wizards $1$, $2$, $3$, and $4$. 110 * From position $3$, we can see wizards $1$, $3$, and $4$. 111 * From position $4$, we can see wizards $1$ and $4$. 112 113 Thus, Harry's list ends up being $[4, 4, 3, 2]$. It can be proved that this is the only possible arrangement. 114 115 In the third test case, it can be proved that Harry could not have obtained his list from any cape arrangement. 116 117 In the fifth case, note that there are two possible cape arrangements from which Harry could have gotten his list: 118 119 * $1 \mid \quad \mid 2 \quad 3 \, \mid$ 120 * $\mid \, 1 \quad 2 \mid \quad \mid 3$