← 返回题目列表

Codeforces · 2065/H

H. 兄弟认为他是他

中文机器翻译题面 查看原题

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$$$ 为模。