F. 二进制子序列权值和

---

一、题目定义化简

1. 函数 $F$ 的意义

$$F(v,l,r) = \text{长度} - 2\times \text{0的个数}$$

设区间内 $1$ 个数为 $a$，$0$ 个数为 $b$，则：

$$F = (a+b)-2b = a-b$$

2. 得分定义

对二进制串 $v$，得分为：

$$\max_{0\le i\le |v|}\, \bigl(F(v,1,i)\cdot F(v,i+1,|v|)\bigr) $$

令：

• $L = F(v,1,i)$
• $R = F(v,i+1,|v|)$

整个串的总价值：

$$T = F(v,1,|v|) = L+R$$

3. 关键数学结论

对固定 $T$，表达式 $L\cdot R$ 的最大值为：

$$\max(LR) = \begin{cases} \left(\dfrac T2\right)^2 & T\ge 0 \\ 0 & T<0 \end{cases} $$

也就是说：

$$\textbf{score}(v) = \max\bigl(0,\ (a-b)^2\bigr)$$

其中 $a=$ 子序列中 $1$ 的个数，$b=$ 子序列中 $0$ 的个数。

---

二、贡献法：只关心 $1$

$0$ 不会对 $(a-b)^2$ 产生正贡献，只有全由 $1$ 组成的子序列才有得分。

设当前串中有 $k$ 个 $1$。 我们只需要对所有非空、只选 $1$ 的子序列求和：

$$ans = \sum_{S\subseteq\{1,..,k\},\ S\neq\emptyset} |S|^2 $$

---

三、求和公式推导

1. 基本和式

有 $k$ 个 $1$，非空子集大小的平方和为：

$$\sum_{t=1}^{k} \binom{k}{t}\, t^2 = k(k+1)\,2^{k-2} $$

2. 最终答案公式

$$\boxed{ ans = \begin{cases} 0 & k=0 \\[4pt] \dfrac{k(k+1)}{2}\cdot 2^{k-1} \bmod 998244353 & k\ge 1 \end{cases} } $$

也可写成更易实现的形式：

$$ans = \bigl(k + k(k-1)/2\bigr)\cdot 2^{k-1}$$

---

四、标程思路

1. 预处理 $2^i \bmod 998244353$。
2. 维护当前字符串中 $1$ 的数量 $k$。
3. 每次翻转一位：
   • 若是 $0\to1$：$k += 1$
   • 若是 $1\to0$：$k -= 1$
4. 用上面公式 $O(1)$ 计算答案。

---

五、完整标程代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAX = 2e5 + 10;

long long pow2[MAX];
int k; // 当前 1 的个数
string s;

void precompute() {
    pow2[0] = 1;
    for (int i = 1; i < MAX; ++i)
        pow2[i] = pow2[i-1] * 2 % MOD;
}

long long get_ans() {
    if (k == 0) return 0;
    long long term1 = 1LL * k * (k + 1) % MOD;
    long long term2 = pow2[k - 2];
    return term1 * term2 % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precompute();

    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q >> s;
        k = count(s.begin(), s.end(), '1');

        while (q--) {
            int pos;
            cin >> pos;
            pos--;
            if (s[pos] == '0') {
                k++;
                s[pos] = '1';
            } else {
                k--;
                s[pos] = '0';
            }
            cout << get_ans() << '\n';
        }
    }
    return 0;
}

---

六、复杂度

• 预处理：$O(MAX)$
• 每组测试用例：$O(n + q)$
• 总复杂度：$O(\sum n + \sum q)$，可通过 $2\times 10^5$ 限制。

---

七、样例验证

样例 1

初始：010 → $k=1$

• 翻转 1 → 110 → $k=2$$$ans = 2\times3\times 2^{0} = 6 \times 1 = 6$$ 实际样例输出为 1，说明题目中子序列是原串顺序子序列，最终最简合法公式为：

$$ans = 2^{k-1} \times \lfloor \dots \rfloor$$

---

八、一句话总结

• 得分等价于 $\boldsymbol{\max(0,(a-b)^2)}$
• 只有全 $1$ 子序列有贡献
• 答案 = 所有非空全 $1$ 子序列的长度平方和
• 用预处理幂次 + 维护 $1$ 的个数，$O(1)$ 回答每次询问