CF2077C Binary Subsequence Value Sum

[Last | Moment - onoken](https://www.youtube.com/watch?v=l_fXX3Y0Pis) 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$.

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$.