CF2255B A Ribbon for Tomorrow

Nephren 从不喜欢冗长的告别。在 Chtholly 即将前往下一个任务之前，她什么也没说，只是开始为她准备一条小丝带。 她把 $n$ 颗玻璃珠子排成一排放在桌上，然后将它们穿到丝带上。每颗珠子要么是白色，要么是黑色。一个二进制字符串 $s$ 描述了它们的颜色：字符 $\mathtt{0}$ 表示白色珠子，字符 $\mathtt{1}$ 表示黑色珠子。 为了让排列变得不那么普通，Nephren 设计了一个小游戏。她可以进行如下操作任意次（包括零次）： - 选择两个下标 $l$ 和 $r$（$1 \le l \le r \le n$），使得当前字符串中 $s_l = s_r$，然后将子串 $s_l s_{l+1}\ldots s_r$ 反转。 例如，如果 $s = \mathtt{00110}$，Nephren 可以选择 $l = 1$ 和 $r = 5$，因为 $s_1 = s_5 = \mathtt{0}$。执行操作后，字符串变成 $\mathtt{01100}$。 请你求出 Nephren 能通过上述操作获得多少种不同的二进制字符串。由于答案可能很大，请将其对 $998\,244\,353$ 取模后输出。 一个二进制字符串是指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。 反转子串 $s_l s_{l+1}\ldots s_r$ 指的是用 $s_r s_{r-1}\ldots s_l$ 替换它。

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

对于每个测试用例，输出一个整数，表示从 $s$ 经过任意次数操作后能获得的不同二进制字符串的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，恰好能获得如下两个字符串： - $\mathtt{00110}$ - $\mathtt{01100}$ 例如，对整个字符串 $\mathtt{00110}$ 反转可得到 $\mathtt{01100}$。 在第二个测试用例中，恰好能获得如下三个字符串： - $\mathtt{001010}$ - $\mathtt{010010}$ - $\mathtt{010100}$ 例如，通过将 $\mathtt{001010}$ 的前四个字符反转，可以得到 $\mathtt{010010}$，反转整个字符串可以得到 $\mathtt{010100}$。 在第三个测试用例中，每个端点相同的子串本身都是回文串，因此任何合法操作都无法改变字符串，只能得到 $\mathtt{01010}$。 在第四个测试用例中，只能得到 $\mathtt{111111}$。 由 ChatGPT 5 翻译