感謝此題將我送上 Master。

思路

注意觀察 \(F(v,l,r)\) 的定義，容易將其刻畫成 \(v_{l \sim r}\) 中 \(1\) 的數量減去 \(0\) 的數量。

不妨將 \(1\) 的權值記作 \(1\)，\(0\) 的權值記作 \(-1\)，令這個序列的權值序列為 \(val_i\)。則對于一個子序列 \(v\) 的得分是 \(\lfloor \frac{S^2}{4} \rfloor\)，其中 \(S = \sum val_i\)?？紤]如下證明：因為無論選擇哪一個點作為分界點其左右兩邊的 \(F\) 函數的和不變，由均值不等式得到該函數的最大值。

那么問題轉化為了求所有子序列的 \(\lfloor \frac{S^2}{4} \rfloor\) 的和，將下取整去掉，即：

注意到 \(val_i\) 的取值并不會影響 \(\sum_T (S_T \bmod 2)\) 的結果，因此原式等價于：

接下來只需要維護所有子序列的 \(\sum S^2\)，即 \(\sum_T(\sum_{x \in T} val_x)^2\)?？紤]拆掉平方項，得：

分別計算 \(\sum_T\sum_{x \in T}val_x^2\) 和 \(2\sum_T\sum_{x,y \in T \wedge x < y}val_x val_y\)。

• 對于前者，注意到 \(\forall i \in T,val_i \in \{1,-1\}\)，因此無論給定字符串是什么 \(val_i^2\) 恒為 \(1\)。即計算 \(\sum_T |T|\)，因為 \(T\) 要非空，因此貢獻為 \(n \times 2^{n - 1}\)。
• 對于后者，考慮計算每一對 \(i < j\) 的貢獻和，即計算 \(2 \sum_{i < j}2^{n - 2}val_i val_j = 2^{n - 1}\sum_{i < j}val_i val_j\)。接下來只需化簡 \(\sum_{i < j}val_i val_j\)，注意到如下等式：

即 \(sum = \sum_{i = 1}^{n}val_i\)，則移項易得 \(\sum_{i < j}val_i val_j = \frac{sum^2 - n}{2}\)。

整理一下可以得到 \(\sum S^2 = n \times 2^{n - 1} + 2^{n - 2} \times (sum^2 - n) = 2^{n - 2} \times (sum^2 + n)\)。答案為：\(\frac{2^{n - 2} \times (sum^2 + n) - 2^{n - 1}}{4}\)。

動態維護 \(sum\) 是容易的。其實完全可以做到區間修改。

Code

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) + (b)) % mod)
#define Sub(a,b) (((a) - (b) + mod) % mod)
#define Mul(a,b) ((a) * (b) % mod)
#define chMul(a,b) (a = Mul(a,b))

using namespace std;

const int mod = 998244353;
const int inv = 748683265;
const int N = 2e5 + 10;
int n,q;
int val[N];
char s[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) chMul(res,a);
        chMul(a,a); b >>= 1;
    } return res;
}

inline void solve(){
    n = read(),q = read();
    scanf("%s",s + 1);
    int sum = 0;
    for (re int i = 1;i <= n;i++) sum += (val[i] = (s[i] == '1') ? 1 : -1);
    while (q--){
        int x; x = read();
        sum -= (2 * val[x]); val[x] = -val[x];
        printf("%lld\n",Mul(Sub(Mul(qmi(2,n - 2 + mod - 1),Add(Mul(sum,sum),n)),qmi(2,n - 1)),inv));
    }
}

signed main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}