codeforces#P2077C. Binary Subsequence Value Sum
Binary Subsequence Value Sum
Description
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$.
Input
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$.
Output
For each test case, output $q$ lines, each line containing a single integer — the required sum modulo $998\,244\,353$.
3
3 2
010
1
3
10 3
0101000110
3
5
10
24 1
011001100110000101111000
24
1
5
512
768
1536
23068672
Note
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$.