CF1762C Binary Strings are Fun

一个长度为奇数 $m$ 的二进制字符串 $^\dagger$ $b$ 被称为“好”的，当且仅当对于所有奇数下标 $i$（$1 \leq i \leq m$），$b_i$ 是 $b[1,i]^\S$ 的中位数 $^\ddagger$。 对于一个长度为 $k$ 的二进制字符串 $a$，长度为 $2k-1$ 的二进制字符串 $b$ 被称为 $a$ 的扩展，当且仅当对于所有 $1 \leq i \leq k$，都有 $b_{2i-1}=a_i$。例如，1001011 和 1101001 都是字符串 1001 的扩展。字符串 $x=1011011$ 不是字符串 $y=1001$ 的扩展，因为 $x_3 \neq y_2$。注意，$a$ 的不同扩展共有 $2^{k-1}$ 个。 给定一个长度为 $n$ 的二进制字符串 $s$。请计算所有 $s$ 的前缀的“好扩展”数量之和。换句话说，求 $\sum_{i=1}^{n} f(s[1,i])$，其中 $f(x)$ 表示字符串 $x$ 的好扩展的数量。由于答案可能很大，只需输出对 $998\,244\,353$ 取模的结果。 $^\dagger$ 二进制字符串是指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。 $^\ddagger$ 对于长度为 $2m-1$ 的二进制字符串 $a$，其中位数是指在 $a$ 中至少出现 $m$ 次的（唯一的）元素。 $^\S$ $a[l,r]$ 表示长度为 $r-l+1$ 的字符串，由 $a_l,a_{l+1},\ldots,a_r$ 按顺序拼接而成。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示二进制字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行答案，对 $998\,244\,353$ 取模。

在第一个和第二个测试用例中，$f(s[1,1])=1$。 在第三个测试用例中，答案为 $f(s[1,1])+f(s[1,2])=1+2=3$。 在第四个测试用例中，答案为 $f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$。 $f(\mathtt{11})=2$，因为有两种好扩展：101 和 111。 $f(\mathtt{01})=1$，因为只有一种好扩展：011。 由 ChatGPT 4.1 翻译