You are given a string $S$ of length $N$ consisting of You are also given $Q$ queries $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$. For $i = 1, 2, \ldots, Q$ in this order, do the following process for the query $(x_i, c_i)$.Problem Statement
0, 1, and ?.
For each $i = 1, 2, \ldots, Q$, $x_i$ is an integer satisfying $1 \leq x_i \leq N$ and $c_i$ is one of the characters 0 , 1, and ?.
? in $S$ with 0 or 1 independently.Constraints
0, 1, and ?.0 , 1, and ?.
Input
Input is given from Standard Input in the following format:
$N$ $Q$ $S$ $x_1$ $c_1$ $x_2$ $c_2$ $\vdots$ $x_Q$ $c_Q$
Output
Print $Q$ lines. For each $i = 1, 2, \ldots, Q$, the $i$-th line should contain the answer to the $i$-th query $(x_i, c_i)$ (that is, the number of strings modulo $998244353$ at the step 2. in the statement).
Sample Input 1
3 3 100 2 1 2 ? 3 ?
Sample Output 1
5 7 10
-
The $1$-st query starts by changing $S$ to
110. Five strings can be obtained as a subsequence of $S = $110:0,1,10,11,110. Thus, the $1$-st query should be answered by $5$. -
The $2$-nd query starts by changing $S$ to
1?0. Two strings can be obtained by the?in $S = $1?0:100and110. Seven strings can be obtained as a subsequence of one of these strings:0,1,00,10,11,100,110. Thus, the $2$-nd query should be answered by $7$. -
The $3$-rd query starts by changing $S$ to
1??. Four strings can be obtained by the?'s in $S = $1??:100,101,110,111. Ten strings can be obtained as a subsequence of one of these strings:0,1,00,01,10,11,100,101,110,111. Thus, the $3$-rd query should be answered by $10$.
Sample Input 2
40 10 011?0??001??10?0??0?0?1?11?1?00?11??0?01 5 0 2 ? 30 ? 7 1 11 1 3 1 25 1 40 0 12 1 18 1
Sample Output 2
746884092 532460539 299568633 541985786 217532539 217532539 217532539 573323772 483176957 236273405
Be sure to print the count modulo $998244353$.
如果这个问题不是动态的，那要怎么做？想到dp做法。
定义 \(dp_{i,0/1}\) 为在前 \(i\) 个字符的所有子序列中，如果再加上 \(0/1\) 这个字符后，就不是前 \(i\) 个字符的子序列了的子序列个数。
那么如果遇到一个 \(1\)，那么就相当于给所有加上 \(1\) 不属于前 \(i\) 个数的子序列加上了一个 \(1\)，\(dp_{i,1}=dp_{i-1,1}\)，然后新生成的这些子序列肯定再加上 \(0\) 后不属于前面的子序列，\(dp_{i,0}=dp_{i-1,1}+dp_{i-1,0}\).
如果遇到一个 \(0\) ，同理。遇到一个问好，\(dp_{i,1}=dp_{i,0}=dp_{i-1,1}+dp_{i-1,0}\)。
另开一个变量统计答案就可以了。
然后就要开始动态 dp，设 \((dp_0,dp_1,ans)\)为一个向量
遇到一个\(1\)，向量乘上 \(\begin{Bmatrix}1&0&0\\1&1&1\\0&0&1 \end{Bmatrix}\)
遇到一个\(0\)，向量乘上 \(\begin{Bmatrix}1&1&1\\0&1&0\\0&0&1 \end{Bmatrix}\)
遇到一个\(?\)，向量乘上 \(\begin{Bmatrix}1&1&1\\1&1&1\\0&0&1 \end{Bmatrix}\)
剩下的就是用线段树维护矩阵乘法，单点修改，区间查询就可以了。
#include<bits/stdc++.h>
const int N=1e5+5,P=998244353;
int n,q,x;
char c;
struct matrix{
int a[4][4];
}t[3],tr[N<<2],p,dw;
matrix cheng(matrix a,matrix b)
{
matrix c;
memset(c.a,0,sizeof(c.a));
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c.a[i][j]+=1LL*a.a[i][k]*b.a[k][j]%P,c.a[i][j]%=P;
return c;
}
int turn(char c)
{
if(c<='1')
return c-'0';
return 2;
}
void copy(matrix&a,matrix b)
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
a.a[i][j]=b.a[i][j];
}
void build(int o,int l,int r)
{
// printf("%d %d %d\n",o,l,r);
if(l>r)
return;
if(l==r)
{
scanf(" %c",&c);
copy(tr[o],t[turn(c)]);
return;
}
int md=l+r>>1;
build(o<<1,l,md);
build(o<<1|1,md+1,r);
copy(tr[o],cheng(tr[o<<1],tr[o<<1|1]));
}
void update(int o,int l,int r,int x,int y)
{
if(l==r)
{
copy(tr[o],t[y]);
return;
}
int md=l+r>>1;
if(md>=x)
update(o<<1,l,md,x,y);
else
update(o<<1|1,md+1,r,x,y);
copy(tr[o],cheng(tr[o<<1],tr[o<<1|1]));
}
int main()
{
scanf("%d%d",&n,&q);
p.a[1][1]=p.a[1][2]=1;
dw.a[1][1]=dw.a[2][2]=dw.a[3][3]=1;
for(int i=0;i<(N<<2);i++)
copy(tr[i],dw);
t[0].a[1][1]=t[0].a[2][1]=t[0].a[2][2]=t[0].a[2][3]=t[0].a[3][3]=1;
t[1].a[1][1]=t[1].a[1][2]=t[1].a[1][3]=t[1].a[2][2]=t[1].a[3][3]=1;
t[2].a[1][1]=t[2].a[1][2]=t[2].a[1][3]=t[2].a[2][1]=t[2].a[2][2]=t[2].a[2][3]=t[2].a[3][3]=1;
build(1,1,n);
while(q--)
{
scanf("%d %c",&x,&c);
update(1,1,n,x,turn(c));
printf("%d\n",cheng(p,tr[1]).a[1][3]);
}
}