codeforces-scrape

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

1762C.md (2448B)


      1 Source: https://codeforces.com/problemset/problem/1762/C
      2 
      3 C. Binary Strings are Fun
      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 A binary string$^\dagger$ $b$ of odd length $m$ is good if $b_i$ is the median$^\ddagger$ of $b[1,i]^\S$ for all odd indices $i$ ($1 \leq i \leq m$).
     22 
     23 For a binary string $a$ of length $k$, a binary string $b$ of length $2k-1$ is an extension of $a$ if $b_{2i-1}=a_i$ for all $i$ such that $1 \leq i \leq k$. For example, 1001011 and 1101001 are extensions of the string 1001. String $x=$1011011 is not an extension of string $y=$1001 because $x_3 \neq y_2$. Note that there are $2^{k-1}$ different extensions of $a$.
     24 
     25 You are given a binary string $s$ of length $n$. Find the sum of the number of good extensions over all prefixes of $s$. In other words, find $\sum_{i=1}^{n} f(s[1,i])$, where $f(x)$ gives number of good extensions of string $x$. Since the answer can be quite large, you only need to find it modulo $998\,244\,353$.
     26 
     27 $^\dagger$ A binary string is a string whose elements are either $\mathtt{0}$ or $\mathtt{1}$.
     28 
     29 $^\ddagger$ For a binary string $a$ of length $2m-1$, the median of $a$ is the (unique) element that occurs at least $m$ times in $a$.
     30 
     31 $^\S$ $a[l,r]$ denotes the string of length $r-l+1$ which is formed by the concatenation of $a_l,a_{l+1},\ldots,a_r$ in that order.
     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 a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), where $n$ is the length of the binary string $s$.
     38 
     39 The second line of each test case contains the binary string $s$ of length $n$.
     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, print the answer modulo $998\,244\,353$.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 1
     55 
     56 1
     57 
     58 1
     59 
     60 0
     61 
     62 2
     63 
     64 11
     65 
     66 3
     67 
     68 010
     69 
     70 9
     71 
     72 101101111
     73 
     74 37
     75 
     76 1011011111011010000011011111111011111
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 1
     83 1
     84 3
     85 3
     86 21
     87 365
     88 ```
     89 
     90 Note
     91 
     92 In the first and second test cases, $f(s[1,1])=1$.
     93 
     94 In the third test case, the answer is $f(s[1,1])+f(s[1,2])=1+2=3$.
     95 
     96 In the fourth test case, the answer is $f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$.
     97 
     98 $f(\mathtt{11})=2$ because two good extensions are possible: 101 and 111.
     99 
    100 $f(\mathtt{01})=1$ because only one good extension is possible: 011.