常见套路(?)
首先，假设是静态。
约定“第 (i) 位”是从高到低的。如 (95731) 的第 (2) 位是 (5)。
推一推方程：
[dp_i = dp_{i-1} imes v_1 + dp_{i-2} imes v_2
]
具体地说，设 (t_i) 是第 (i) 位上的数字，(u) 是第 (i-1) 位与第 (i) 位拼成的数字，即 (10t_{i-1} + t_i)。则
[dp_i = dp_{i-1} imes (t_i + 1) + [10 leq u leq 18]dp_{i-2} imes (19 - u)
]
然后看到非独立的修改操作，套路就出场了：线段树维护矩阵乘法
大概就是把 (dp) 的转移换成矩阵乘法，然后用线段树单点修改，维护一些区间的积。
这里就不展开讨论了，可以找一些资料。
对每个位置 (i) 可构造矩阵
[egin{pmatrix} 0 & v_{2_i} \ 1 & v_{1_i} end{pmatrix}
quad
]
然后应该就不难了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=998244353;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(int &x,int y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
#define check(x) if(x >= mod) x -= mod
int n,m,dp[500005],t[500005];
char s[500005];
struct mat{
int a[2][2];
mat(){a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;}
}E;
mat operator *(mat a,mat b){
mat c;
rep(i,0,1) rep(j,0,1) rep(k,0,1) {c.a[i][j] += (ll)a.a[i][k] * b.a[k][j] % mod;check(c.a[i][j]);}
return c;
}
mat st[500005];
struct segtree{
mat dat[1048580];int n;
void build(int nn)
{
n=1;
while(n<=nn) n<<=1;
for(int i=n-1;i<2*n-1;i++) dat[i]=st[i - n + 1];
for(int i=n-2;i>=0;i--) dat[i] = dat[(i<<1)+1] * dat[(i<<1)+2];
}
void update(int k,mat a){
k+=n-1;
dat[k]=a;
while(k>0){
k=(k-1)/2;
dat[k]=dat[(k<<1)+1]*dat[(k<<1)+2];
}
}
mat query(int l,int r){
return query(l,r+1,0,0,n);
}
mat query(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return E;
if(a<=l&&r<=b) return dat[k];
return query(a,b,(k<<1)+1,l,(l+r)>>1)*query(a,b,(k<<1)+2,(l+r)>>1,r);
}
}seg;
int main()
{
E.a[0][0] = E.a[1][1] = 1;
scanf("%d%d%s",&n,&m,s+1);
rep(i,1,n) t[i] = s[i] - 48;
/*dp[0] = 1;
rep(i,1,n) {
dp[i] = ((ll)dp[i - 1] * (t[i] + 1))% mod;
int u = t[i] + t[i - 1] * 10;
if(i > 1 && 10 <= u && u <= 18) {dp[i] += (ll)dp[i - 2] * (19 - u) % mod;check(dp[i]);}
}
printf("%d
",dp[n]);*/
st[0] = E;
rep(i,1,n) {
int u = t[i] + t[i - 1] * 10;
st[i].a[0][0] = 0;
st[i].a[0][1] = (i > 1 && 10 <= u && u <= 18 ? 19 - u : 0);
st[i].a[1][0] = 1;
st[i].a[1][1] = t[i] + 1;
}
seg.build(n);
//mat res = seg.query(1,n);
//printf("%d %d
%d %d
",res.a[0][0],res.a[0][1],res.a[1][0],res.a[1][1]);
rep(i,1,m) {
int a,b;
scanf("%d%d",&a,&b);
t[a] = b;
int u1 = t[a] + t[a - 1] * 10, u2 = t[a + 1] + t[a] * 10;
st[a].a[0][1] = (a > 1 && 10 <= u1 && u1 <= 18 ? 19 - u1 : 0);
st[a].a[1][1] = t[a] + 1;
seg.update(a, st[a]);
if(a < n) st[a + 1].a[0][1] = (10 <= u2 && u2 <= 18 ? 19 - u2 : 0),seg.update(a + 1, st[a + 1]);
mat res = seg.query(1,n);
printf("%d
",res.a[1][1]);
}
return 0;
}