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