2237D.md (3310B)
1 Source: https://codeforces.com/problemset/problem/2237/D 2 3 D. Fullmetal Bitchemist 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 A binary string is a string consisting only of characters $0$ and $1$. The two characters $0$ and $1$ are called opposite values. 22 23 Consider a binary string $t$. Let $|t|$ be the length of $t$. When $|t| \ge 2$, for every $1 \le i \lt |t|$, the characters $t_i$ and $t_{i+1}$ are adjacent. 24 25 A binary string $t$ is called beautiful if it can be reduced to a string of length exactly $1$ by applying the following operation any number of times, possibly zero: 26 27 * Choose two equal adjacent characters, remove both of them, and insert one character with the opposite value in their place. 28 29 For example, the string $\mathtt{10001}$ can become $\mathtt{1101}$ by replacing the first adjacent pair $\mathtt{00}$ with $\mathtt{1}$. Then it can become $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$. Therefore, $\mathtt{10001}$ is beautiful. 30 31 On the other hand, $\mathtt{111}$ is not beautiful. After one operation, it becomes $\mathtt{01}$, and then no operation can be applied. 32 33 You are given a binary string $s$. Compute the number of non-empty beautiful substrings$^{\text{∗}}$ of $s$. 34 35 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. 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 an integer $n$ ($1 \le n \le 10^6$) — the length of $s$. 42 43 The second line of each test case contains a binary string $s$ of length $n$. 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 beautiful substrings of $s$. 50 51 Example 52 53 Input 54 55 ``` 56 10 57 58 1 59 60 0 61 62 2 63 64 01 65 66 5 67 68 01001 69 70 3 71 72 001 73 74 6 75 76 011110 77 78 9 79 80 010110110 81 82 12 83 84 010000101001 85 86 16 87 88 1010011010010110 89 90 20 91 92 11110101101101001110 93 94 30 95 96 000101100011111001111100000010 97 ``` 98 99 Output 100 101 ``` 102 1 103 104 2 105 106 10 107 108 5 109 110 15 111 112 30 113 114 47 115 116 81 117 118 139 119 120 316 121 ``` 122 123 Note 124 125 In the first test case, the only non-empty substring is $\mathtt{0}$, which is already a binary string of length $1$. Therefore, it is beautiful. 126 127 In the second test case, the beautiful substrings are $\mathtt{0}$ and $\mathtt{1}$. The substring $\mathtt{01}$ is not beautiful, because its two characters are not equal, so no operation can be applied. 128 129 In the third test case, the beautiful substrings are: 130 131 * $s[1,1]=\mathtt{0}$; 132 * $s[2,2]=\mathtt{1}$; 133 * $s[3,3]=\mathtt{0}$; 134 * $s[4,4]=\mathtt{0}$; 135 * $s[5,5]=\mathtt{1}$; 136 * $s[3,4]=\mathtt{00}$, which can become $\mathtt{1}$; 137 * $s[2,4]=\mathtt{100}$, which can become $\mathtt{11}$, then $\mathtt{0}$; 138 * $s[3,5]=\mathtt{001}$, which can become $\mathtt{11}$, then $\mathtt{0}$; 139 * $s[1,4]=\mathtt{0100}$, which can become $\mathtt{011}$, then $\mathtt{00}$, then $\mathtt{1}$; 140 * $s[1,5]=\mathtt{01001}$, which can become $\mathtt{0111}$, then $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$. 141 142 Thus, there are $10$ beautiful substrings.