2061C.md (2405B)
1 Source: https://codeforces.com/problemset/problem/2061/C 2 3 C. Kevin and Puzzle 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 Kevin enjoys logic puzzles. 22 23 He played a game with $n$ classmates who stand in a line. The $i$-th person from the left says that there are $a_i$ liars to their left (not including themselves). 24 25 Each classmate is either honest or a liar, with the restriction that no two liars can stand next to each other. Honest classmates always say the truth. Liars can say either the truth or lies, meaning their statements are considered unreliable. 26 27 Kevin wants to determine the number of distinct possible game configurations modulo $998\,244\,353$. Two configurations are considered different if at least one classmate is honest in one configuration and a liar in the other. 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 an integer $n$ ($1\leq n \leq 2 \cdot 10^5$) — the number of classmates. 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0\leq a_i \leq n$) — the number of liars to the left of the $i$-th person they claimed. 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 test case, output one integer — the number of distinct game configurations modulo $998\,244\,353$. 42 43 Example 44 45 Input 46 47 ``` 48 8 49 50 3 51 52 0 1 2 53 54 5 55 56 0 0 0 0 0 57 58 5 59 60 0 0 1 1 2 61 62 5 63 64 0 1 2 3 4 65 66 5 67 68 0 0 1 1 1 69 70 5 71 72 5 1 5 2 5 73 74 1 75 76 0 77 78 4 79 80 2 3 1 1 81 ``` 82 83 Output 84 85 ``` 86 1 87 2 88 3 89 0 90 4 91 1 92 2 93 0 94 ``` 95 96 Note 97 98 We will use $\color{red}{\text{red}}$ to mark liars and $\color{blue}{\text{blue}}$ to mark honest people. 99 100 In the first test case, the only possible way is $(\color{red}{0},\color{blue}{1},\color{red}{2})$. 101 102 In the second test case, two possible ways are $(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$ and $(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$. 103 104 In the third test case, three possible ways are $(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})$, $(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})$, $(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{blue}{1},\color{red}{2})$.