Make it Alternating
题意翻译
[SA](https://www.luogu.com.cn/user/409236) 有一个 01 串 $s$。Sp 认为 01 相间的 01 串才是美丽的,因此 SA 提供一种操作,可以删除 $s$ 某一位上的字符。
你需要输出:
- 使得 $s$ 01 相间需要的最少操作次数。
- 有多少种不同最短的操作序列使得 $s$ 01 相间,对 $998244353$ 取模。一个操作序列是由每次删除的字符在目前串中的位置顺次组成的。两个操作序列 $p,q$ 不同当且仅当存在一个位置 $i$ 满足 $p_i=q_i$。
Translated by [Shunpower](https://www.luogu.com.cn/user/399150).
题目描述
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 \le i \le |s| $ , then erase the character $ s_i $ .
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 \le t \le 10^4 $ ) — the number of test cases.
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.
Additional constraint on the input:
- the total length of strings $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
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 $ .
输入输出样例
输入样例 #1
3
10010
111
0101
输出样例 #1
1 2
2 6
0 1
说明
In the first test case of the example, the shortest sequences of operations are:
- $ [2] $ (delete the $ 2 $ -nd character);
- $ [3] $ (delete the $ 3 $ -rd character).
In the second test case of the example, the shortest sequences of operations are:
- $ [2, 1] $ (delete the $ 2 $ -nd character, then delete the $ 1 $ -st character);
- $ [2, 2] $ ;
- $ [1, 1] $ ;
- $ [1, 2] $ ;
- $ [3, 1] $ ;
- $ [3, 2] $ .
In the third test case of the example, the only shortest sequence of operations is $ [] $ (empty sequence).