1879C.md (2115B)
1 Source: https://codeforces.com/problemset/problem/1879/C 2 3 C. Make it Alternating 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 You are given a binary string $s$. A binary string is a string consisting of characters 0 and/or 1. 22 23 You can perform the following operation on $s$ any number of times (even zero): 24 25 * choose an integer $i$ such that $1 \le i \le |s|$, then erase the character $s_i$. 26 27 You have to make $s$ alternating, i. e. after you perform the operations, every two adjacent characters in $s$ should be different. 28 29 Your goal is to calculate two values: 30 31 * the minimum number of operations required to make $s$ alternating; 32 * the number of different shortest sequences of operations that make $s$ alternating. Two sequences of operations are different if in at least one operation, the chosen integer $i$ is different in these two sequences. 33 34 Input 35 36 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 37 38 Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$). The string $s$ consists of characters 0 and/or 1 only. 39 40 Additional constraint on the input: 41 42 * the total length of strings $s$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, print two integers: the minimum number of operations you have to perform, and the number of different shortest sequences of operations. Since the second number might be large, print its remainder modulo $998244353$. 47 48 Example 49 50 Input 51 52 ``` 53 3 54 55 10010 56 57 111 58 59 0101 60 ``` 61 62 Output 63 64 ``` 65 1 2 66 2 6 67 0 1 68 ``` 69 70 Note 71 72 In the first test case of the example, the shortest sequences of operations are: 73 74 * $[2]$ (delete the $2$-nd character); 75 * $[3]$ (delete the $3$-rd character). 76 77 In the second test case of the example, the shortest sequences of operations are: 78 79 * $[2, 1]$ (delete the $2$-nd character, then delete the $1$-st character); 80 * $[2, 2]$; 81 * $[1, 1]$; 82 * $[1, 2]$; 83 * $[3, 1]$; 84 * $[3, 2]$. 85 86 In the third test case of the example, the only shortest sequence of operations is $[]$ (empty sequence).