前置：广义矩阵乘法
定义广义矩阵乘法 \(A * B = C\) 为：
\[C_{i,j}=\bigoplus_{k}(A_{i,k} \bigotimes B_{k,j})
\]
其中 $ \bigoplus $ 与 $ \bigotimes $ 是两种二元运算
当 $ \bigoplus $运算满足交换律 ， $ \bigotimes $ 运算满足交换律，且 $ \bigotimes $ 对 $ \bigoplus $ 存在分配律，即存在 \((\bigoplus a) \bigotimes b=\bigoplus (a \bigotimes b)\) 时，广义矩阵乘法满足结合律
动态 \(DP\)
思想：将 \(DP\) 方程的转移写成矩阵乘法的形式，使用数据结构快速维护矩阵乘法达到快速解出 \(DP\) 式的目的
例题
AT_abc246_h [ABC246Ex] 01? Queries
设 $ dp_{i,0/1} $ 表示当前遍历到第几个，最后一个数是 \(0/1\)
有状态转移方程式：
\[dp_{i,0} = \begin{cases}
dp_{i-1,0},x_i=1\\
dp_{i-1,0}+dp_{i-1,1},\text{otherwise}
\end{cases}
\]
\[dp_{i,1} = \begin{cases}
dp_{i-1,1},x_i=0\\
dp_{i-1,0}+dp_{i-1,1},\text{otherwise}
\end{cases}
\]
转换为矩阵乘法形式
\[\begin{bmatrix}
dp_{i,0} \\
dp_{i,1} \\
1
\end{bmatrix}=
\begin{cases}\begin{bmatrix}1 & 1 & 1 \\0 & 1 & 0 \\0 & 0 & 1 \end{bmatrix}\begin{bmatrix}dp_{i-1,0} \\dp_{i-1,1} \\1\end{bmatrix},x_i=0\\\begin{bmatrix}1 & 0 & 0 \\1 & 1 & 1 \\0 & 0 & 1 \end{bmatrix}\begin{bmatrix}dp_{i-1,0} \\dp_{i-1,1} \\1\end{bmatrix},x_i=1\\\begin{bmatrix}1 & 1 & 1 \\1 & 1 & 1 \\0 & 0 & 1 \end{bmatrix}\begin{bmatrix}dp_{i-1,0} \\dp_{i-1,1} \\1\end{bmatrix},x_i=?\\
\end{cases}
\]
线段树维护即可
#include<bits/stdc++.h>
#define fre(ss,i,j,k) for(int ss=i;ss<=j;ss+=k)
using namespace std;
using namespace FastIOS;
const int N=1e5+5;
const long long mod=998244353;
int n,m;
char a[N];
struct Matrix{long long jz[4][4];void init(){memset(jz,0,sizeof(jz));}Matrix(){init();}auto operator[](int x){return jz[x];}Matrix operator*(const Matrix&other)const{Matrix c;memset(c.jz,0,sizeof c.jz);fre(i,1,3,1)fre(j,1,3,1)fre(k,1,3,1)c.jz[i][j]=(c.jz[i][j]+jz[i][k]*other.jz[k][j]%mod)%mod;return c;}
}mat[N],bit[3],ans,s[N<<2];
void build(int rt,int l,int r){if(l==r){s[rt]=mat[l];return;}int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);s[rt]=s[rt<<1]*s[rt<<1|1];
}
void update(int rt,int l,int r,int x){if(l==r){s[rt]=mat[l];return;}int mid=(l+r)>>1;if(x<=mid)update(rt<<1,l,mid,x);else update(rt<<1|1,mid+1,r,x);s[rt]=s[rt<<1]*s[rt<<1|1];
}
Matrix query(int rt,int l,int r,int x,int y){if(x<=l&&r<=y)return s[rt];int mid=(l+r)>>1;if(mid<x)return query(rt<<1|1,mid+1,r,x,y);else if(mid>=y)return query(rt<<1,l,mid,x,y);else return query(rt<<1,l,mid,x,y)*query(rt<<1|1,mid+1,r,x,y);
}main(){ans[1][1]=1,ans[1][2]=0,ans[1][3]=0;ans[2][1]=0,ans[2][2]=1,ans[2][3]=0;ans[3][1]=0,ans[3][2]=0,ans[3][3]=1;bit[0][1][1]=1,bit[0][1][2]=1,bit[0][1][3]=1;bit[0][2][1]=0,bit[0][2][2]=1,bit[0][2][3]=0;bit[0][3][1]=0,bit[0][3][2]=0,bit[0][3][3]=1;bit[1][1][1]=1,bit[1][1][2]=0,bit[1][1][3]=0;bit[1][2][1]=1,bit[1][2][2]=1,bit[1][2][3]=1;bit[1][3][1]=0,bit[1][3][2]=0,bit[1][3][3]=1;bit[2][1][1]=1,bit[2][1][2]=1,bit[2][1][3]=1;bit[2][2][1]=1,bit[2][2][2]=1,bit[2][2][3]=1;bit[2][3][1]=0,bit[2][3][2]=0,bit[2][3][3]=1;n=rd(),m=rd();fre(i,1,n,1)a[i]=gc(),mat[i]=bit[a[i]=='?'?2:a[i]-'0'];build(1,1,n);while(m--){int x=rd();char y=gc();a[x]=y,mat[x]=bit[a[x]=='?'?2:a[x]-'0'],update(1,1,n,x);Matrix ask=ans*query(1,1,n,1,n);wt((ask[1][3]+ask[2][3])%mod),pc('\n');}ios_end();
}
【模板】动态 DP
相同的套路
设 \(dp_{i,0/1}\) 表示选/不选当前点
状态转移方程式:
\[dp_{u,0}=\sum_{v\in son_u} \max(dp_{v,0},dp_{v,1})\\
dp_{u,1}=a_u + \sum_{v\in son_u} dp_{v,0}
\]
定义此时广义矩阵乘法 \(A * B = C\) 为：
\[C_{i,j}=\max{k}(A_{i,k} + B_{k,j})
\]
则有
\[\begin{bmatrix}
dp_{u,0} \\
dp_{u,1}
\end{bmatrix}=\sum_{v \in sum_u}
\begin{bmatrix}
1 & 1 \\
a_i & -INF
\end{bmatrix}
\begin{bmatrix}
dp_{v,0} \\
dp_{v,1}
\end{bmatrix}
\]
树链剖分+dfs序上线段树维护单点修改即可
#include<bits/stdc++.h>
#define fre(ss,i,j,k) for(int ss=i;ss<=j;ss+=k)
using namespace std;
using namespace FastIOS;
const int N=1e5,L=3;
int n,m,a[N+5],sz[N+5],heavy[N+5],top[N+5],par[N+5],dep[N+5],dfn[N+5],mxdfn[N+5],fdfn[N+5],dfstime,dp[N+5][2];
vector<int>q[N+5];
struct Matrix{long long jz[3][3];Matrix(){memset(jz,0,sizeof(jz));}auto operator[](int x){return jz[x];}Matrix operator*(const Matrix&other)const{Matrix c;memset(c.jz,0,sizeof c.jz);fre(i,1,2,1)fre(j,1,2,1)fre(k,1,2,1)c.jz[i][j]=max(c.jz[i][j],jz[i][k]+other.jz[k][j]);return c;}
}s[N<<2],mat[N+5];
void dfs1(int u,int fa){sz[u]=1,par[u]=fa,dep[u]=dep[fa]+1,dp[u][1]=a[u];int maxsize=0;for(auto v:q[u])if(v!=fa){dfs1(v,u),sz[u]+=sz[v];dp[u][0]+=max(dp[v][1],dp[v][0]),dp[u][1]+=dp[v][0];if(sz[v]>maxsize)maxsize=sz[v],heavy[u]=v;}
}
void dfs2(int u,int cha){top[u]=cha,dfn[u]=++dfstime,fdfn[dfstime]=u,mxdfn[cha]=dfstime;if(heavy[u])dfs2(heavy[u],cha);mat[u][2][1]=a[u];for(auto v:q[u])if(v!=par[u]&&v!=heavy[u])dfs2(v,v),mat[u][1][1]+=max(dp[v][0],dp[v][1]),mat[u][2][1]+=dp[v][0];mat[u][1][2]=mat[u][1][1];
}
void build(int rt,int l,int r){if(l==r){s[rt]=mat[fdfn[l]];return;}int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);s[rt]=s[rt<<1]*s[rt<<1|1];
}
Matrix query(int rt,int l,int r,int x,int y){if(x<=l&&r<=y)return s[rt];int mid=(l+r)>>1;if(mid<x)return query(rt<<1|1,mid+1,r,x,y);else if(mid>=y)return query(rt<<1,l,mid,x,y);else return query(rt<<1,l,mid,x,y)*query(rt<<1|1,mid+1,r,x,y);
}
void update(int rt,int l,int r,int x){if(l==r){s[rt]=mat[fdfn[l]];return;}int mid=(l+r)>>1;if(x<=mid)update(rt<<1,l,mid,x);else update(rt<<1|1,mid+1,r,x);s[rt]=s[rt<<1]*s[rt<<1|1];
}
void change(int x,int val){mat[x][2][1]+=(val-a[x]),a[x]=val;while(x){Matrix lst=query(1,1,n,dfn[top[x]],mxdfn[top[x]]);update(1,1,n,dfn[x]);Matrix now=query(1,1,n,dfn[top[x]],mxdfn[top[x]]);x=par[top[x]];if(!x)break;mat[x][1][1]+=max(now[1][1],now[2][1])-max(lst[1][1],lst[2][1]);mat[x][1][2]=mat[x][1][1];mat[x][2][1]+=now[1][1]-lst[1][1];}
}
main(){cin>>n>>m;fre(i,1,n,1)cin>>a[i];fre(i,1,n-1,1){int u,v;cin>>u>>v;q[u].push_back(v),q[v].push_back(u);}dfs1(1,0),dfs2(1,1),build(1,1,n);while(m--){int x,y;cin>>x>>y,change(x,y);Matrix ans=query(1,1,n,dfn[1],mxdfn[1]);cout<<max(ans[1][1],ans[2][1])<<'\n';}
}