C. Binary Subsequence Value Sum
combinatorics; data structures; dp; fft; math; matrices
Last | Moment - onoken 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: IndicesSubsequenceScore\(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: IndicesSubsequenceScore\(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\).