CF1930I Counting Is Fun

给定一个长度为 $n$ 的二进制模式串 $p$。 如果一个长度同为 $n$ 的二进制字符串 $q$ 满足：对于每一个 $i$（$1 \leq i \leq n$），都存在区间 $[l, r]$，使得： - $1 \leq l \leq i \leq r \leq n$，且 - $p_i$ 是字符串 $q_lq_{l+1}\ldots q_r$ 的众数， 则称 $q$ 为一个“好”二进制字符串。 请计算有多少个“好”二进制字符串，答案对 $998\,244\,353$ 取模。 注： $^\dagger$ 二进制字符串是仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。 $^\ddagger$ 字符 $c$ 是长度为 $m$ 的字符串 $t$ 的众数，如果 $c$ 在 $t$ 中出现的次数不少于 $\lceil \frac{m}{2} \rceil$。例如，$\mathtt{0}$ 是 $\mathtt{010}$ 的众数，$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数，$\mathtt{0}$ 和 $\mathtt{1}$ 都是 $\mathtt{011010}$ 的众数。

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示二进制字符串 $p$ 的长度。 第二行输入一个长度为 $n$ 的二进制字符串 $p$，仅包含字符 $0$ 和 $1$。

输出“好”二进制字符串的个数，对 $998\,244\,353$ 取模。

在第二个样例中，所有的“好”字符串为： - $\mathtt{010}$； - $\mathtt{011}$； - $\mathtt{101}$； - $\mathtt{110}$； - $\mathtt{111}$。 由 ChatGPT 4.1 翻译