题解：P15495 [ICPC 2025 APC] Tower of Hanoi
Phi_Mobius
·
·
题解
线段树维护动态 DP。不错的练手题咋没人做。
不太需要脑子的矩阵写法。
考虑 \Theta(nq) 做法。修改直接改，对于静态问题，我们有如下的 DP。假设序列 a_i\in\{1,2,3\}，计算三柱汉诺塔最小步数。
设 dp_{i,j} 表示前 i 个盘从初始状态到全部摞在第 j 个柱子上的状态所需的最小步数。
我们考虑第 i 个也就是最大的盘，如果它已经在目标柱 j，则直接继承 dp_{i-1,j} 即可，否则需要三步：
- 先把前 i-1 个盘全部放到“除了 a_i 和 j 之外的第三个柱”（即第 6-a_i-j 个柱）上。
- 然后把第 i 个盘放到目标柱 j。
- 最后把这个 6-a_i-j 号柱上的塔挪到第 j 个柱上。
形式化地，我们有：
dp_{i,j}=
\begin{cases}
dp_{i-1,j}&a_i=j,\\
dp_{i-1,6-j-a_i}+1+f_{i-1}\quad &\text{otherwise}.
\end{cases}
其中 f_k 表三柱汉诺塔中把 k 个盘的塔完整挪到另一个塔上的最小步数（初始其他两柱皆为空），由上文类似的推导过程有 f_k=2f_{k-1}+1，解得 f_k=2^k-1。于是当 a_i\ne j 时，dp_{i,j}=dp_{i-1,6-j-a_i}+1+f_{i-1}=dp_{i-1,6-j-a_i}+2^{i-1}。
静态就做完了。发现状态很小，用矩阵描述这个转移。三个 a_i 对应三个不同的转移矩阵，以 a_i=1 为例：
\begin{bmatrix}
1&0&0&0\\
0&0&1&1\\
0&1&0&1\\
0&0&0&2
\end{bmatrix}
\times
\begin{bmatrix}
dp_{i-1,1}\\
dp_{i-1,2}\\
dp_{i-1,3}\\
2^{i-1}
\end{bmatrix}
=
\begin{bmatrix}
dp_{i,1}\\
dp_{i,2}\\
dp_{i,3}\\
2^i
\end{bmatrix}
::::success[AC Code]
常数较大。
三个转移矩阵可以用好看一点的方法预处理的，但是我懒得改。
```cpp line-numbers
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#define int long long
using namespace std;
const int N=1e5+7,MOD=998244353;
int a[N];
struct matrix{
int n,m;
int a[5][5];
friend matrix operator*(matrix a,matrix b){
matrix c={a.n,b.m,{0}};
if(a.m!=b.n) return c;
for(int i=1;i<=c.n;i++)
for(int k=1;k<=a.m;k++)
for(int j=1;j<=c.m;j++)
(c.a[i][j]+=a.a[i][k]*b.a[k][j])%=MOD;
return c;
}
}I={4,4,{{},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0},
{0,0,0,0,1}
}},A={4,1,{
{},{},{},{},
{0,1},}},
M[4]={
{0,0,{}},
{4,4,{{},
{0,1,0,0,0},
{0,0,0,1,1},
{0,0,1,0,1},
{0,0,0,0,2}}},
{4,4,{{},
{0,0,0,1,1},
{0,0,1,0,0},
{0,1,0,0,1},
{0,0,0,0,2}}},
{4,4,{{},
{0,0,1,0,1},
{0,1,0,0,1},
{0,0,0,1,0},
{0,0,0,0,2}}}
};
struct node{
int l,r;
matrix mtrx;
}tr[N<<2];
void build(int u,int l,int r){
tr[u]={l,r,M[a[l]]};
if(l==r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
tr[u].mtrx=tr[u<<1|1].mtrx*tr[u<<1].mtrx;
}
void upd(int u,int x,int k){
if(tr[u].l>x || tr[u].r<x) return ;
if(tr[u].l==tr[u].r){
tr[u].mtrx=M[k];
return ;
}
upd(u<<1,x,k),upd(u<<1|1,x,k);
tr[u].mtrx=tr[u<<1|1].mtrx*tr[u<<1].mtrx;
}
matrix ask(int u,int l,int r){
if(tr[u].l>r || tr[u].r<l) return I;
if(tr[u].l>=l && tr[u].r<=r) return tr[u].mtrx;
return ask(u<<1|1,l,r)*ask(u<<1,l,r);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(q--){
char op;
int l,r,x,y;
cin>>op;
if(op=='c'){
cin>>x>>y;
upd(1,x,y);
}
if(op=='s'){
cin>>l>>r;
matrix ans=ask(1,l,r)*A;
cout<<ans.a[1][1]<<'\n';
}
}
return 0;
}
```
::::