Skibidus 认为他就是他!他通过解决这项艰巨的任务证明了这一点。你也能证明自己吗?
给定一个二进制字符串$$$^{\text{*}}$$$ $$$t$$$,$$$f(t)$$$ 被定义为连续子字符串的最小数量,每个子字符串由相同的字符组成,$$$t$$$ 可以被划分为这些子字符串。例如,$$$f(\texttt{00110001}) = 4$$$,因为 $$$t$$$ 可以分区为 $$$\texttt{[00][11][000][1]}$$$,其中每个括号内的段由相同的字符组成。
Skibidus 为您提供二进制字符串 $$$s$$$ 和 $$$q$$$ 查询。在每个查询中,字符串的单个字符被翻转(即 $$$\texttt{0}$$$ 更改为 $$$\texttt{1}$$$ 和 $$$\texttt{1}$$$ 更改为 $$$\texttt{0}$$$);处理查询后保存更改。每次查询后,输出所有 $$$f(b)$$$ 的总和,其中 $$$b$$$ 是 $$$s$$$ 的非空子序列$$$^{\text{†}}$$$,模 $$$998\,244\,353$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个二进制字符串 $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$)。
每个测试用例的以下行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。
下面一行包含 $$$q$$$ 整数 $$$v_1, v_2, \ldots, v_q$$$ ($$$1 \leq v_i \leq |s|$$$),表示 $$$s_{v_i}$$$ 对于第 $$$i$$$ 查询被翻转。
保证所有测试用例的 $$$|s|$$$ 之和与 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在一行上输出 $$$q$$$ 整数 - 每个查询后的答案以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 101 2 1 3 10110 3 1 2 3 101110101 5 7 2 4 4 1
输出 #1
10 7 61 59 67 1495 1169 1417 1169 1396
注意
在第一个测试用例中,第一个查询后 $$$s$$$ 变为 $$$\texttt{001}$$$。让我们计算每个子序列的答案:
- $$$f(s_1) = f(\texttt{0}) = 1$$$
- $$$f(s_2) = f(\texttt{0}) = 1$$$
- $$$f(s_3) = f(\texttt{1}) = 1$$$
- $$$f(s_1 s_2) = f(\texttt{00}) = 1$$$
- $$$f(s_1 s_3) = f(\texttt{01}) = 2$$$
- $$$f(s_2 s_3) = f(\texttt{01}) = 2$$$
- $$$f(s_1 s_2 s_3) = f(\texttt{001}) = 2$$$
这些值的总和为 $$$10$$$,以 $$$998\,244\,353$$$ 为模。