题意：
定义一种特殊的加法，这种加法没有进位，其他与普通加法一样，比如16+16=212。
给出一个数，询问这个数可能被哪两个数用特殊加法构成，并且每次询问修改这个数数位上的一个数字，输出更新后的答案。
题解：
矩阵乘法可以用来加速线性递推式。
以斐波那契数列为例：
f[n] = f[n-1] + f[n-2]
可以构造出矩阵A：
f[n-1] f[n-2]
需要转移到状态B：
f[n] f[n-1]
要构造一个转移矩阵X，使得AX=B。由矩阵乘法的性质可得，X是一个2*2的矩阵。
f[n-1]*x(1,1) + f[n-2]*x(1,2) f[n-1]*x(2,1) + f[n-2]*x(2,2)
又由斐波那契数列的递推式可以得知这个X是这样的：
1 1 1 0
这就是转移矩阵了。将原始的矩阵(f[1],f[2])乘上n-2次后，x(1,1)就是答案。
在这基础上用矩阵快速幂优化，可以把时间复杂度从O(n)优化到O(8*logn)。
对于这道题，面对带修改的线性dp，考虑用线段树维护矩阵乘法。
（1）先不考虑修改，不考虑区间，直接列出整个区间的DP方程。
（2）列出转移矩阵，由于有很多修改操作，我们将数据集中在一起处理，还可以利用矩阵结合律，并且区间比较好提取。
（3）线段树维护矩阵。对于修改，在矩阵上做修改，对于不同的题目，我们要用不同的修改方式。
对于这道题，对于一个字符串c，可以写出下面的递推式
f(i) = f(i-1)*(c[i]+1)+f(i-2)*(19-c[i-1]*10-c[i])
面对这个转移矩阵，根据上面斐波那契的方法，我们可以写出转移矩阵：
c[i]+1 (19-c[i-1]*10-c[i]) 1 0
然后写到这里，俺蒙蔽了，回头想通了补。。。
看了橙名大佬的代码才知道是线段树维护矩阵乘法，涨姿势了，%%%%%%%
//线段树维护矩阵乘法 #include<bits/stdc++.h> using namespace std; const int maxn=5e5+100; const int mod=998244353; typedef long long ll; struct node { ll sum[2][2]; int l,r; }segTree[maxn*4]; void update (int x) { segTree[x].l=segTree[x<<1].l; segTree[x].r=segTree[x<<1|1].r; for (int i=0;i<2;i++) for (int j=0;j<2;j++) { segTree[x].sum[i][j]=segTree[x<<1].sum[i][1]*segTree[x<<1|1].sum[1][j]%mod; int y=segTree[x<<1].r*10+segTree[x<<1|1].l; if (y>=10&&y<=18) { segTree[x].sum[i][j]+=segTree[x<<1].sum[i][0]*segTree[x<<1|1].sum[0][j]%mod*(9-(y-9)+1)%mod; if (segTree[x].sum[i][j]>=mod) segTree[i].sum[i][j]%=mod; } } } ll a[maxn]; void build (int x,int l,int r) { if (l==r) { segTree[x].l=segTree[x].r=a[l]; segTree[x].sum[1][1]=segTree[x].l+1; segTree[x].sum[0][0]=0; segTree[x].sum[0][1]=segTree[x].sum[1][0]=1; return; } int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); update(x); } void modify (int x,int l,int r,int pos,int d) { if (l==r) { segTree[x].l=segTree[x].r=d; segTree[x].sum[1][1]=segTree[x].l+1; segTree[x].sum[0][0]=0; segTree[x].sum[0][1]=segTree[x].sum[1][0]=1; return; } int mid=(l+r)>>1; if (mid>=pos) modify(x<<1,l,mid,pos,d); else modify(x<<1|1,mid+1,r,pos,d); update(x); } int n,m,x,y; string s; int main () { scanf("%d%d",&n,&m); cin>>s; for (int i=0;i<s.length();i++) a[i+1]=s[i]-'0'; build(1,1,n); while (m--) { scanf("%d%d",&x,&y); modify(1,1,n,x,y); printf("%lld\n",segTree[1].sum[1][1]); } }
原文链接: https://www.cnblogs.com/zhanglichen/p/13337174.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368206
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
