Binary Strings are Fun

题目描述

A binary string $ ^\dagger $ $ b $ of odd length $ m $ is good if $ b_i $ is the median $ ^\ddagger $ of $ b[1,i]^\S $ for all odd indices $ i $ ( $ 1 \leq i \leq m $ ). For a binary string $ a $ of length $ k $ , a binary string $ b $ of length $ 2k-1 $ is an extension of $ a $ if $ b_{2i-1}=a_i $ for all $ i $ such that $ 1 \leq i \leq k $ . For example, 1001011 and 1101001 are extensions of the string 1001. String $ x= $ 1011011 is not an extension of string $ y= $ 1001 because $ x_3 \neq y_2 $ . Note that there are $ 2^{k-1} $ different extensions of $ a $ . You are given a binary string $ s $ of length $ n $ . Find the sum of the number of good extensions over all prefixes of $ s $ . In other words, find $ \sum_{i=1}^{n} f(s[1,i]) $ , where $ f(x) $ gives number of good extensions of string $ x $ . Since the answer can be quite large, you only need to find it modulo $ 998\,244\,353 $ . $ ^\dagger $ A binary string is a string whose elements are either $ \mathtt{0} $ or $ \mathtt{1} $ . $ ^\ddagger $ For a binary string $ a $ of length $ 2m-1 $ , the median of $ a $ is the (unique) element that occurs at least $ m $ times in $ a $ . $ ^\S $ $ a[l,r] $ denotes the string of length $ r-l+1 $ which is formed by the concatenation of $ a_l,a_{l+1},\ldots,a_r $ in that order.

输入输出格式

输入格式

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. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ), where $ n $ is the length of the binary string $ s $ . The second line of each test case contains the binary string $ s $ of length $ n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print the answer modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111

输出样例 #1

1
1
3
3
21
365

说明

In the first and second test cases, $ f(s[1,1])=1 $ . In the third test case, the answer is $ f(s[1,1])+f(s[1,2])=1+2=3 $ . In the fourth test case, the answer is $ f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3 $ . $ f(\mathtt{11})=2 $ because two good extensions are possible: 101 and 111. $ f(\mathtt{01})=1 $ because only one good extension is possible: 011.

**题目大意：**

二进制字符串很有趣。一个长度为奇数 \( m \) 的二进制字符串 \( b \) 是好的，如果对于所有奇数索引 \( i \) （\( 1 \leq i \leq m \)），\( b_i \) 是 \( b[1,i] \) 的中位数。对于长度为 \( k \) 的二进制字符串 \( a \)，长度为 \( 2k-1 \) 的二进制字符串 \( b \) 是 \( a \) 的扩展，如果对于所有 \( 1 \leq i \leq k \) 的 \( i \)，都有 \( b_{2i-1}=a_i \)。给定一个长度为 \( n \) 的二进制字符串 \( s \)，求所有 \( s \) 前缀的好扩展数量的总和。换句话说，找到 \( \sum_{i=1}^{n} f(s[1,i]) \)，其中 \( f(x) \) 返回字符串 \( x \) 的好扩展数量。由于答案可能很大，只需要找到它模 \( 998\,244\,353 \) 的结果。

**输入输出数据格式：**

**输入格式：**

每个测试包含多个测试用例。第一行包含测试用例数 \( t \)（\( 1 \le t \le 10^4 \)）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 2 \cdot 10^5 \)），其中 \( n \) 是二进制字符串 \( s \) 的长度。

每个测试用例的第二行包含长度为 \( n \) 的二进制字符串 \( s \)。

保证所有测试用例的 \( n \) 之和不超过 \( 2 \cdot 10^5 \)。

**输出格式：**

对于每个测试用例，以模 \( 998\,244\,353 \) 的形式打印答案。**题目大意：** 二进制字符串很有趣。一个长度为奇数 \( m \) 的二进制字符串 \( b \) 是好的，如果对于所有奇数索引 \( i \) （\( 1 \leq i \leq m \)），\( b_i \) 是 \( b[1,i] \) 的中位数。对于长度为 \( k \) 的二进制字符串 \( a \)，长度为 \( 2k-1 \) 的二进制字符串 \( b \) 是 \( a \) 的扩展，如果对于所有 \( 1 \leq i \leq k \) 的 \( i \)，都有 \( b_{2i-1}=a_i \)。给定一个长度为 \( n \) 的二进制字符串 \( s \)，求所有 \( s \) 前缀的好扩展数量的总和。换句话说，找到 \( \sum_{i=1}^{n} f(s[1,i]) \)，其中 \( f(x) \) 返回字符串 \( x \) 的好扩展数量。由于答案可能很大，只需要找到它模 \( 998\,244\,353 \) 的结果。 **输入输出数据格式：** **输入格式：** 每个测试包含多个测试用例。第一行包含测试用例数 \( t \)（\( 1 \le t \le 10^4 \)）。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 2 \cdot 10^5 \)），其中 \( n \) 是二进制字符串 \( s \) 的长度。 每个测试用例的第二行包含长度为 \( n \) 的二进制字符串 \( s \)。 保证所有测试用例的 \( n \) 之和不超过 \( 2 \cdot 10^5 \)。 **输出格式：** 对于每个测试用例，以模 \( 998\,244\,353 \) 的形式打印答案。