AT_abc246_h

因为刚刚见过类似的题，所以一眼就看出来了。

Description

给定长度为 n 的序列，每一个位置可能是 0,1,? 中的一个。

每一次会修改一个位置，查询整个序列在每一个 ? 被替换成 0 或 1 的情况下的可能的非空子序列的个数。

Solution

非空子序列，想到 dp。

定义 dp_{i,j} 表示当前考虑前 i 位，最后一位是 j 的答案。j\in \{0,1\}。

特殊的，如果 a_i=j，钦定最后一位在 i。

转移：

发现这个转移式子的系数跟 dp 的值没有关系。

所以可以写成矩阵。

• a_i=0 \begin{bmatrix} dp_{i-1,0} & dp_{i-1,1} & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} dp_{i,0} & dp_{i,1} & 1 \end{bmatrix}
• a_i=1 \begin{bmatrix} dp_{i-1,0} & dp_{i-1,1} & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 1 & 1 \end{bmatrix} = \begin{bmatrix} dp_{i,0} & dp_{i,1} & 1 \end{bmatrix}
• a_i=? \begin{bmatrix} dp_{i-1,0} & dp_{i-1,1} & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} dp_{i,0} & dp_{i,1} & 1 \end{bmatrix}

因为矩阵乘法是有结合律的，所以线段树维护就完了。

复杂度 O(T^3(n+q\log n))，T 是矩阵大小，这里 T=3。

Code

#include<bits/stdc++.h>
#define int long long
#define F(i,a,b) for(int i=a;i<=(b);i++)
#define dF(i,a,b) for(int i=a;i>=(b);i--)
using namespace std;
const int MAXN=1e5+5;
const int mod=998244353;
int n,q,a[MAXN];
struct matrix{
    int z[3][3];
    int* operator [](int x){return z[x];}
    inline void clear(){F(i,0,2)F(j,0,2)z[i][j]=0;}
    inline friend matrix operator *(matrix a,matrix b){
        matrix c;c.clear();
        F(k,0,2)F(i,0,2)F(j,0,2){
            (c[i][j]+=a[i][k]*b[k][j]%mod)%=mod;
        }
        return c;
    }
    inline void set(int opt){
        if(opt==0){
            z[0][0]=1;z[0][1]=0;z[0][2]=0;
            z[1][0]=1;z[1][1]=1;z[1][2]=0;
            z[2][0]=1;z[2][1]=0;z[2][2]=1;
        }
        if(opt==1){
            z[0][0]=1;z[0][1]=1;z[0][2]=0;
            z[1][0]=0;z[1][1]=1;z[1][2]=0;
            z[2][0]=0;z[2][1]=1;z[2][2]=1;
        }
        if(opt==-1){
            z[0][0]=1;z[0][1]=1;z[0][2]=0;
            z[1][0]=1;z[1][1]=1;z[1][2]=0;
            z[2][0]=1;z[2][1]=1;z[2][2]=1;
        }
    }
}st;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
matrix tr[MAXN<<2];
void build(int l,int r,int q){
    if(l==r){
        tr[q].set(a[l]);
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ls(q));
    build(mid+1,r,rs(q));
    tr[q]=tr[ls(q)]*tr[rs(q)];
}
void update(int l,int r,int ql,int q){
    if(l==r){
        tr[q].set(a[l]);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)update(l,mid,ql,ls(q));
    if(mid<ql)update(mid+1,r,ql,rs(q));
    tr[q]=tr[ls(q)]*tr[rs(q)];
}
inline int gnum(char x){
    if(x=='?')return -1;
    return x-'0';
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>q;st.clear();st[0][2]=1;
    F(i,1,n){
        char c;cin>>c;
        a[i]=gnum(c);
    }
    build(1,n,1);
    while(q--){
        int x;char c;cin>>x>>c;
        a[x]=gnum(c);
        update(1,n,x,1);
        matrix ans=st*tr[1];
        int res=(ans[0][0]+ans[0][1])%mod;
        cout<<res<<"\n";
    }
}