题意回顾

对于一个二进制字符串 $v$，定义

$$F(v,l,r) = (r-l+1) - 2 \times (\text{区间内 0 的个数})$$

并且 $F(v,l,r) = 0$ 若 $l > r$。

定义 $\text{score}(v) = \max\limits_{0 \le i \le |v|} \big[ F(v,1,i) \times F(v,i+1,|v|) \big]$。

给定一个长度为 $n$ 的二进制字符串 $s$，有 $q$ 次修改（每次翻转某一位），每次修改后要求所有非空子序列的得分之和，对 $998244353$ 取模。

---

第一步：简化得分公式

对于子序列 $v$，设其有 $z$ 个 $0$、$o$ 个 $1$，总长度 $L = z+o$。

考虑 $v$ 的一个前缀，设其中有 $a$ 个 $0$、$b$ 个 $1$，则：

$$F(\text{前缀}) = (a+b) - 2a = b-a$$

对应的后缀有 $z-a$ 个 $0$、$o-b$ 个 $1$，则：

$$F(\text{后缀}) = (o-b) - (z-a) = (o-z) - (b-a)$$

记 $d = b-a$，则得分 = $\max\limits_d [\, d \cdot ((o-z) - d) \,]$。

这是一个关于 $d$ 的二次函数 $d(\Delta - d)$，其中 $\Delta = o-z$。

它在 $d = \Delta/2$ 处取得最大值 $\Delta^2/4$，由于 $d$ 必须是整数且可达，实际最大值为：

$$\text{score}(v) = \left\lfloor \frac{\Delta^2}{4} \right\rfloor $$

其中 $\Delta = (\text{1 的个数}) - (\text{0 的个数})$。

---

第二步：转化为组合计数

设原串中 $1$ 的总数为 $O$，$0$ 的总数为 $Z$（$O+Z=n$）。

一个子序列由选择若干个 $1$ 和若干个 $0$ 组成（位置决定子序列的唯一性）。
对于给定的 $(o,z)$，这样的子序列个数为 $\binom{O}{o} \cdot \binom{Z}{z}$。

因此，所有非空子序列的得分之和为：

$$\text{ans} = \sum_{o=0}^{O} \sum_{z=0}^{Z} \binom{O}{o} \binom{Z}{z} \cdot \left\lfloor \frac{(o-z)^2}{4} \right\rfloor $$

其中 $(o,z) \neq (0,0)$，但 $o=z=0$ 时 $\Delta=0$，贡献为 $0$，所以包含在内无影响。

---

第三步：按 $\Delta$ 分组

令 $d = o-z$，则 $o = z+d$。

固定 $d$，$z$ 的范围：$\max(0, -d) \le z \le \min(Z, O-d)$。

此时：

$$\text{cnt}[d] = \sum_{z=\max(0,-d)}^{\min(Z, O-d)} \binom{O}{z+d} \binom{Z}{z} $$

于是：

$$\text{ans} = \sum_{d=-Z}^{O} \text{cnt}[d] \cdot \left\lfloor \frac{d^2}{4} \right\rfloor $$

---

第四步：简化 $\text{cnt}[d]$

考虑生成函数：

$$\sum_{d} \text{cnt}[d] x^d = \sum_{z} \sum_{o} \binom{O}{o} \binom{Z}{z} x^{o-z} $$$$= \left( \sum_{o} \binom{O}{o} x^o \right) \left( \sum_{z} \binom{Z}{z} x^{-z} \right) $$$$= (1+x)^O \cdot (1+x^{-1})^Z$$ $$= (1+x)^O \cdot x^{-Z} (1+x)^Z$$ $$= x^{-Z} (1+x)^{O+Z} = x^{-Z} (1+x)^n$$

因此，$\text{cnt}[d]$ 是 $(1+x)^n$ 中 $x^{d+Z}$ 的系数，即：

$$\text{cnt}[d] = \binom{n}{d+Z}$$

---

第五步：代入得简洁公式

令 $k = d+Z$，则 $k$ 从 $0$ 到 $n$，$d = k-Z$。

于是：

$$\text{ans} = \sum_{k=0}^{n} \binom{n}{k} \cdot \left\lfloor \frac{(k-Z)^2}{4} \right\rfloor $$

其中 $Z$ 是当前字符串中 $0$ 的个数。

---

第六步：模运算处理

$\lfloor (k-Z)^2 / 4 \rfloor = \frac{(k-Z)^2 - r(k)}{4}$，其中 $r(k) = (k-Z)^2 \bmod 4$。

所以：

$$\text{ans} = \frac{1}{4} \left[ \sum_{k=0}^{n} \binom{n}{k} (k-Z)^2 - \sum_{k=0}^{n} \binom{n}{k} r(k) \right] $$

---

第一部分：$\sum \binom{n}{k} (k-Z)^2$

利用公式：

$$\sum_{k=0}^{n} \binom{n}{k} k = n 2^{n-1}$$ $$\sum_{k=0}^{n} \binom{n}{k} k^2 = n(n-1) 2^{n-2} + n 2^{n-1} $$$$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

所以：

$$\sum_{k=0}^{n} \binom{n}{k} (k-Z)^2 = \left[ n(n-1)2^{n-2} + n2^{n-1} \right] - 2Z \cdot n2^{n-1} + Z^2 \cdot 2^n $$

---

第二部分：$\sum \binom{n}{k} r(k)$

$r(k) = (k-Z)^2 \bmod 4$，只依赖于 $(k-Z) \bmod 4$。

设 $t = (k-Z) \bmod 4$，则 $r(k) = t^2 \bmod 4 = \begin{cases} 0, & t \text{ 偶} \\ 1, & t \text{ 奇} \end{cases}$

所以 $r(k)=1$ 当且仅当 $k \equiv Z+1$ 或 $Z+3 \pmod{4}$。

因此：

$$\sum_{k=0}^{n} \binom{n}{k} r(k) = \sum_{k \equiv Z+1 \pmod{4}} \binom{n}{k} + \sum_{k \equiv Z+3 \pmod{4}} \binom{n}{k} $$

---

如何计算 $\sum_{k \equiv a \pmod{4}} \binom{n}{k}$ 模 $998244353$

利用单位根 $\omega = i$（模 $998244353$ 下存在，因为 $998244353 \equiv 1 \pmod{4}$）。

公式：

$$\sum_{k \equiv a \pmod{4}} \binom{n}{k} = \frac{1}{4} \sum_{j=0}^{3} \omega^{-ja} (1+\omega^j)^n $$

其中 $\omega = 911660635$（原根 $3$ 的 $(998244353-1)/4$ 次幂），满足 $\omega^2 \equiv -1$。

---

第七步：动态维护

每次翻转一位，$Z$ 变化 $\pm 1$，$O$ 也随之变化。
但注意公式中只依赖 $Z$，因为 $n$ 固定。

所以每次修改后：

1. 更新 $Z$（$0$ 的个数）
2. 用上面公式计算新的 $\text{ans}$

计算复杂度 $O(1)$ 每次修改（因为单位根求和是固定的 $4$ 项）。

---

第八步：最终算法

预处理：

• $2^n, 2^{n-1}, 2^{n-2}$（模 $998244353$）
• 单位根 $\omega$ 及其幂次
• 初始 $Z$

每次修改：

• 更新 $Z$
• 计算：

$$\text{sum1} = \big[ n(n-1)2^{n-2} + n2^{n-1} \big] - 2Z \cdot n2^{n-1} + Z^2 \cdot 2^n $$$$\text{sum2} = \sum_{k \equiv Z+1 \pmod{4}} \binom{n}{k} + \sum_{k \equiv Z+3 \pmod{4}} \binom{n}{k} \quad (\text{用单位根公式}) $$$$\text{ans} = \frac{\text{sum1} - \text{sum2}}{4} \pmod{998244353} $$

输出 $\text{ans}$。

---

时间复杂度

预处理 $O(1)$，每次修改 $O(1)$，总复杂度 $O(n + q)$ 每个测试用例，满足要求。