T0885 价值

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

/*
价值：01 串 t 的价值 = max_{0<=i<=|t|} g(t,1,i) * g(t,i+1,|t|)，
其中 g 是子串里「1 的个数 - 0 的个数」。

关键结论：设 S = 该子序列的 1 数 - 0 数，则价值恰为 floor(S^2 / 4)。
  证明：记前缀和 P_i = g(t,1,i)，则 g(t,i+1,|t|) = S - P_i，
        P_i(S-P_i) 关于 P_i 是开口向下的抛物线，整数上最大值是 floor(S^2/4)；
        而从 0 走到 S 的 ±1 路径必然经过 floor(S/2)，那里正好取到 floor(S^2/4)。

再算「所有非空子序列的价值之和」：
  设子序列的失衡值为 S，生成函数 prod_i (1 + x^{w_i}) = x^{-q}(1+x)^n
  （q 为 0 的个数，w_i = ±1），所以失衡值为 S 的子序列个数是 C(n, S+q)。
  于是答案 = sum_{k=0}^{n} C(n,k) * floor((k-q)^2 / 4)。
  用二项式定理化简：
      sum C(n,k)(k-q)^2 = n(n+1)2^{n-2} - 2qn·2^{n-1} + q^2·2^n
      sum C(n,k)((k-q) mod 2) = 2^{n-1}
  得答案 = 2^n * (n(n+1) - 4qn + 4q^2 - 2) / 16。
  注意答案只与 n 和当前 0 的个数 q 有关，与 0/1 的排列无关！
*/

const long long MOD = 998244353;

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int zeros = 0;
    for (char c : s) if (c == '0') zeros++;

    const long long INV16 = modpow(16, MOD - 2);
    long long p2 = modpow(2, n);

    while (q--) {
        int pos;
        cin >> pos;
        --pos;
        if (s[pos] == '0') { s[pos] = '1'; zeros--; }
        else { s[pos] = '0'; zeros++; }

        long long nn = n % MOD;
        long long zz = zeros % MOD;
        long long bracket = (nn * ((nn + 1) % MOD) % MOD
                             - 4 * nn % MOD * zz % MOD
                             + 4 * zz % MOD * zz % MOD
                             - 2) % MOD;
        if (bracket < 0) bracket += MOD;
        long long ans = p2 * INV16 % MOD * bracket % MOD;
        cout << ans << "\n";
    }
    return 0;
}