2 seconds
256 megabytes
standard input
standard output
You are given a binary string s�. A binary string is a string consisting of characters 0 and/or 1.
You can perform the following Operation on s� any number of times (even zero):
- choose an integer i� such that 1≤i≤|s|1≤�≤|�|, then erase the character si��.
You have to make s� alternating, i. e. after you perform the operations, every two adjacent characters in s� should be different.
Your goal is to calculate two values:
- the minimum number of operations required to make s� alternating;
- 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.
The first line contains one integer t� (1≤t≤1041≤�≤104) — the number of test cases.
Each test case consists of one line containing the string s� (1≤|s|≤2⋅1051≤|�|≤2⋅105). The string s� consists of characters 0 and/or 1 only.
Additional constraint on the input:
- the total length of strings s� over all test cases does not exceed 2⋅1052⋅105.
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 998244353998244353.
1 2 2 6 0 1
In the first test case of the example, the shortest sequences of operations are:
- [2][2] (delete the 22-nd character);
- [3][3] (delete the 33-rd character).
In the second test case of the example, the shortest sequences of operations are:
- [2,1][2,1] (delete the 22-nd character, then delete the 11-st character);
- [2,2][2,2];
- [1,1][1,1];
- [1,2][1,2];
- [3,1][3,1];
- [3,2][3,2].
In the third test case of the example, the only shortest sequence of operations is [][] (empty sequence).
This post first appeared on Clara's Random Thoughts - This Is My Home Where My, please read the originial post: here
