codeforces-scrape

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

2255B.md (3020B)


      1 Source: https://codeforces.com/problemset/problem/2255/B
      2 
      3 B. A Ribbon for Tomorrow
      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 Nephren has never been fond of long farewells. Before Chtholly leaves for her next mission, she says nothing and begins preparing a small ribbon for her instead.
     22 
     23 She places $n$ glass beads in a row on the table before threading them onto the ribbon. Each bead is either white or black. A binary$^{\text{∗}}$ string $s$ represents their colors: the character $\mathtt{0}$ represents a white bead, and the character $\mathtt{1}$ represents a black bead.
     24 
     25 To make the arrangement less ordinary, Nephren turns it into a small game. She can perform the following operation any number of times (possibly zero):
     26 
     27 * Choose two indices $l$ and $r$ ($1 \le l \le r \le n$) such that $s_l=s_r$ in the current string, and reverse$^{\text{†}}$ the substring $s_l s_{l+1}\ldots s_r$.
     28 
     29 For example, if $s=\mathtt{00110}$, Nephren may choose $l=1$ and $r=5$, since $s_1=s_5=\mathtt{0}$. After the operation, the string becomes $\mathtt{01100}$.
     30 
     31 Determine the number of different binary strings that can be obtained from $s$. Since this number may be large, output it modulo $998\,244\,353$.
     32 
     33 $^{\text{∗}}$A binary string is a string where each character is either $\mathtt 0$ or $\mathtt 1$.
     34 
     35 $^{\text{†}}$To reverse a substring $s_l s_{l+1}\ldots s_r$ means to replace it with $s_r s_{r-1}\ldots s_l$.
     36 
     37 Input
     38 
     39 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.
     40 
     41 The first line of each test case contains one integer $n$ ($1 \le n \le 10^6$) — the number of beads.
     42 
     43 The second line contains a binary string $s$ of length $n$, describing the colors of the beads.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
     46 
     47 Output
     48 
     49 For each test case, output a single integer — the number of different binary strings that can be obtained from $s$, modulo $998\,244\,353$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 
     58 5
     59 
     60 00110
     61 
     62 6
     63 
     64 001010
     65 
     66 5
     67 
     68 01010
     69 
     70 6
     71 
     72 111111
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 2
     79 
     80 3
     81 
     82 1
     83 
     84 1
     85 ```
     86 
     87 Note
     88 
     89 In the first test case, exactly the following two strings can be obtained:
     90 
     91 * $\mathtt{00110}$;
     92 * $\mathtt{01100}$.
     93 
     94 For example, reversing the entire string $\mathtt{00110}$ produces $\mathtt{01100}$.
     95 
     96 In the second test case, exactly the following three strings can be obtained:
     97 
     98 * $\mathtt{001010}$;
     99 * $\mathtt{010010}$;
    100 * $\mathtt{010100}$.
    101 
    102 For example, $\mathtt{010010}$ can be obtained by reversing the first four characters of $\mathtt{001010}$, and $\mathtt{010100}$ can be obtained by reversing the entire string $\mathtt{001010}$.
    103 
    104 In the third test case, every substring whose endpoints contain the same character is a palindrome. Therefore, reversing any valid substring does not change the string, and only $\mathtt{01010}$ can be obtained.
    105 
    106 In the fourth test case, we can only get $\mathtt{111111}$.