codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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})$.