codeforces-scrape

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

2256B.md (2493B)


      1 Source: https://codeforces.com/problemset/problem/2256/B
      2 
      3 B. Domino Tiles
      4 
      5 time limit per test
      6 
      7 1 second
      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 Nygglatho returns from the market with an old box of tiles whose painted marks have begun to fade. Before she can put it away, Chtholly and the young fairies have already spread the tiles across the dining table and turned them into a puzzle.
     22 
     23 There is a row of $n$ tiles. Each tile should be marked with either $\mathtt 0$ or $\mathtt 1$. However, some of the marks have faded away.
     24 
     25 The current row is represented by a string $s$ of length $n$. Each character of $s$ is $\mathtt{0}$, $\mathtt{1}$, or $\mathtt{?}$. Chtholly must replace every $\mathtt{?}$ with either $\mathtt{0}$ or $\mathtt{1}$.
     26 
     27 After replacement, for every $1 \le i \lt n$, the two neighboring tiles $s_i$ and $s_{i+1}$ form a domino of weight $(s_i + s_{i+1})$. Note that two consecutive dominoes share exactly one tile. The completed row is valid if every two consecutive dominoes have different weights.
     28 
     29 Determine the number of different$^{\text{∗}}$ ways to replace all $\mathtt{?}$ characters so that the completed row is valid. Output the answer modulo $998\,244\,353$.
     30 
     31 $^{\text{∗}}$Two ways of replacement are considered different if the resulting strings are different.
     32 
     33 Input
     34 
     35 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.
     36 
     37 The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of tiles.
     38 
     39 The second line contains the string $s$ of length $n$, where $s_i= \mathtt{0}$, $\mathtt{1}$, or $\mathtt{?}$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output one integer — the number of valid ways to replace all $\mathtt{?}$ characters, modulo $998\,244\,353$.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 2
     55 
     56 ??
     57 
     58 5
     59 
     60 0?1??
     61 
     62 5
     63 
     64 0?0??
     65 
     66 8
     67 
     68 00110011
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 4
     75 
     76 2
     77 
     78 0
     79 
     80 1
     81 ```
     82 
     83 Note
     84 
     85 In the first test case, there is only one domino, so every completion is valid. The valid completed strings are $\mathtt{00}$, $\mathtt{01}$, $\mathtt{10}$, and $\mathtt{11}$.
     86 
     87 In the second test case, the valid completed strings are $\mathtt{00110}$ and $\mathtt{01100}$.
     88 
     89 In the third test case, there are no valid completed strings.
     90 
     91 In the fourth test case, the only valid completed string is $\mathtt{00110011}$.