For a binary string$$$^{\text{∗}}$$$ $$$v$$$, the score of $$$v$$$ is defined as the maximum value of
$$$$$$F\big(v, 1, i\big) \cdot F\big(v, i+1, |v|\big)$$$$$$
over all $$$i$$$ ($$$0 \leq i \leq |v|$$$).
Here, $$$F\big(v, l, r\big) = r - l + 1 - 2 \cdot \operatorname{zero}(v, l, r)$$$, where $$$\operatorname{zero}(v, l, r)$$$ denotes the number of $$$\mathtt{0}$$$s in $$$v_lv_{l+1} \ldots v_r$$$. If $$$l > r$$$, then $$$F\big(v, l, r\big) = 0$$$.
You are given a binary string $$$s$$$ of length $$$n$$$ and a positive integer $$$q$$$.
You will be asked $$$q$$$ queries.
In each query, you are given an integer $$$i$$$ ($$$1 \leq i \leq n$$$). You must flip $$$s_i$$$ from $$$\mathtt{0}$$$ to $$$\mathtt{1}$$$ (or from $$$\mathtt{1}$$$ to $$$\mathtt{0}$$$). Find the sum of the scores over all non-empty subsequences$$$^{\text{†}}$$$ of $$$s$$$ after each modification query.
Since the result may be large, output the answer modulo $$$998\,244\,353$$$.
Note that the modifications are persistent.
$$$^{\text{∗}}$$$A binary string is a string that consists only of the characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.
$$$^{\text{†}}$$$A binary string $$$x$$$ is a subsequence of a binary string $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly zero or all) characters.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — the length of the string $$$s$$$ and the number of modification queries, respectively.
The second line contains the binary string $$$s$$$ of length $$$n$$$, consisting of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.
The following $$$q$$$ lines each contain an integer $$$i$$$ ($$$1 \leq i \leq n$$$), indicating that $$$s_i$$$ is flipped from $$$\mathtt{0}$$$ to $$$\mathtt{1}$$$ or from $$$\mathtt{1}$$$ to $$$\mathtt{0}$$$.
It is guaranteed that neither the total sum of all values of $$$n$$$ nor the total sum of all values of $$$q$$$ across all test cases exceeds $$$2 \cdot 10^5$$$.
For each test case, output $$$q$$$ lines, each line containing a single integer — the required sum modulo $$$998\,244\,353$$$.
33 20101310 30101000110351024 101100110011000010111100024
1 5 512 768 1536 23068672
For the first test case, after the first modification, we have $$$s = \texttt{110}$$$. We can compute the sum of scores over all subsequences as follows:
| Indices | Subsequence | Score |
| $$$1$$$ | 1 | $$$0$$$ |
| $$$2$$$ | 1 | $$$0$$$ |
| $$$1, 2$$$ | 11 | $$$1$$$ |
| $$$3$$$ | 0 | $$$0$$$ |
| $$$1, 3$$$ | 10 | $$$0$$$ |
| $$$2, 3$$$ | 10 | $$$0$$$ |
| $$$1, 2, 3$$$ | 110 | $$$0$$$ |
Summing up: $$$0+0+1+0+0+0+0 = 1$$$.
After the second modification, we have $$$s = \texttt{111}$$$. We can compute the sum of scores over all subsequences as follows:
| Indices | Subsequence | Score |
| $$$1$$$ | 1 | $$$0$$$ |
| $$$2$$$ | 1 | $$$0$$$ |
| $$$1, 2$$$ | 11 | $$$1$$$ |
| $$$3$$$ | 1 | $$$0$$$ |
| $$$1, 3$$$ | 11 | $$$1$$$ |
| $$$2, 3$$$ | 11 | $$$1$$$ |
| $$$1, 2, 3$$$ | 111 | $$$2$$$ |
Summing up: $$$0+0+1+0+1+1+2 = 5$$$.
| Codeforces Round 1008 (Div. 1) |
|---|
| Finished |
