浅谈状压 DP
wangxx2012
·
·
算法·理论
状压 DP，即用二进制（也有可能是其他进制）把原来复杂的状态压缩，再做 DP。
用这种方法解决题目的数据范围都很小。
位运算
对于一个二进制数 x，有以下技巧：
- 取出第 i 位。
y=(x>>(i-1))&1;
- 将第 i 位取反。
x^=(1<<(i-1));
- 将第 i 位变为 1。
x|=1<<(i-1);
- 将第 i 位变为 0。
x&=(~(1<<(i-1)));
- 判断第 i 位是否为 1。
if(x&(1<<(i-1)));
- 枚举子集。
for(int i=x;i;i=(i-1)&x) cout<<i;
原理：通过不断将当前子集 i 减去 1，再与原始集合 x 取按位与，从而得到 x 的下一个更小的子集。
时间复杂度：O(2^{\text{popcount}(x)})，\text{popcount}(x) 指 x 中 1 的个数。
1. 棋盘式状压
这类问题通常在一个棋盘上进行。我们将一行的状态压缩成一个二进制数，然后逐行进行转移，确保当前行的状态不与上一行冲突。
解决此类问题的一般步骤：
- 定义 dp，一般形式为 dp_{i,s} 表示第 i 行为状态 s，如有其他状态可增加维数。
- 设计状态转移方程。
- 找约束条件。
- 枚举状态，在满足约束条件的情况下，实现状态转移。
例题 1：[SCOI2005] 互不侵犯
:::info[题意]{open}
在 N \times N 的棋盘上放置 K 个国王，国王可以攻击周围 8 个相邻的格子。要求任意两个国王都不互相攻击。求不同的放置方案数。
:::
当做棋盘式状压的模板是不错的。逐行转移。
定义 dp_{i,s,k} 为第 i 行状态为 s 且已经放了 k 个国王。
状态 s 为一个二进制数，若第 i 位为 1，则表示在这一位置上放国王，否则就不放。
那么有转移方程
dp_{i,s,k}=\sum dp_{i-1,s',k-cnt_s}
考虑如何使得状态合法。
首先，我们可以预处理出左右不同时为 $1$ 的所有状态。而对于判断上下两行相同位置是否同为 $1$，按位与即可，左右相邻就往左或右移一位。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=1e3+10;
int n,K;
struct node{
int s,cnt;//s表示状态，cnt表示状态s中有多少个1
}zt[maxn];
int tot;
int dp[10][maxn][100];
int get(int x){//获取1的个数
int cnt=0;
while(x){
if(x%2) cnt++;
x/=2;
}
return cnt;
}
void init(){//预处理相邻不同为1的状态
for(int i=0;i<(1<<n);i++){
if(i&(i<<1)) continue;
zt[++tot].s=i;
zt[tot].cnt=get(i);
dp[1][tot][zt[tot].cnt]=1;
}
}
bool check(int x,int y){//约束条件
return !((x&y)||(x&(y>>1)||(x&(y<<1))));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>K;
init();
for(int i=2;i<=n;i++){//枚举行数
for(int j=1;j<=tot;j++){//枚举第i行状态
for(int k=zt[j].cnt;k<=K;k++){//枚举放置国王数
for(int h=1;h<=tot;h++){//枚举第i-1行的状态
if(check(zt[j].s,zt[h].s)) dp[i][j][k]+=dp[i-1][h][k-zt[j].cnt];
}
}
}
}
int ans=0;
for(int i=1;i<=tot;i++) ans+=dp[n][i][K];//方案总数
cout<<ans;
return 0;
}
```
:::
## 例题 2：[[USACO06NOV] Corn Fields G](https://www.luogu.com.cn/problem/P1879)
:::info[题意]{open}
有一个 $M$ 行 $N$ 列的网格，每个格子是 $0$（不能种草）或 $1$（可以种草）。要在可以种草的格子中选出一些格子种上草，且没有两块草地在上下左右四个方向上相邻。求所有可能的种植方案数，结果对 $10^8$ 取模。
:::
定义 $dp_{i,s}$ 为第 $i$ 行且状态为 $s$ 的状态数。
同理，当 $s$ 的第 $i$ 为 $1$ 时，表示种草，否则就不种。
则有
$$
dp_{i,s}=\sum dp_{i-1,s'}
$$
思考有几个约束。
+ 同一行相邻位置不能同时为 $1$。
+ 上下两行相同位置不能同时为 $1$。
+ 为 $1$ 的位置不能是贫瘠的。
前两点像前一道题那样判断即可，考虑如何满足第三点。
我们可以用另开一个数组 $\text{mp}$，$\text{mp}_i$ 用来记录第 $i$ 行哪些位置是肥沃的（同样用二进制，$1$ 表示肥沃，$0$ 表示贫瘠），然后拿它与选择土地的状态做判断。
判断相同位置为 $1$ 是简单的，所以考虑将 $\text{mp}_i$ 取反，再按位与判断。
不要忘了取模。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=2e3+10;
const int mod=1e8;
int n,m;
int mp[maxn],zt[maxn];//mp表示i位置的土地是否肥沃,zt记录状态
int dp[20][maxn];
int tot;
void init(){//预处理相邻不同为1的状态
for(int i=0;i<(1<<m);i++){
if(i&(i<<1)) continue;
zt[++tot]=i;
}
}
bool check1(int i,int j){//约束条件
return !((~mp[i])&zt[j]);
}
bool check2(int i,int j){//约束条件
return !(zt[i]&zt[j]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
if(x) mp[i]+=(1<<(m-j));
}
}
init();
dp[0][1]=1;
for(int i=1;i<=n;i++){//枚举行数
for(int s1=1;s1<=tot;s1++){//枚举第i行的状态
if(!check1(i,s1)) continue;
for(int s2=1;s2<=tot;s2++){//枚举第i-1行的状态
if(!check1(i-1,s2)) continue;
if(check2(s1,s2)){
dp[i][s1]+=dp[i-1][s2];
dp[i][s1]%=mod;
}
}
}
}
int ans=0;
for(int i=1;i<=tot;i++) ans+=dp[n][i],ans%=mod;//方案总数
cout<<ans;
return 0;
}
```
:::
## 例题 3：[[NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704)
:::info[题意]{open}
给定一个 $N \times M$ 的网格，每个格子为山地或平原。在平原上可以部署炮兵，每个炮兵的攻击范围为：同一行中左右各两格、同一列中上下各两格。要求任意两个炮兵不能互相攻击，即不存在两个炮兵使得它们在同一行且列距 $\le 2$，或同一列且行距 $\le 2$。
求最多能部署的炮兵数量。
:::
前两题的结合 + 升级。
由于这道题第 $i$ 行的状态被第 $i-1$ 行和 $i-2$ 行约束，我们将原本的二维 $dp$ 扩到三维。
定义 $dp_{i,s1,s2}$ 表示第 $i$ 行状态为 $s1$，第 $i-1$ 行状态为 $s2$ 的最大摆放数。
则有
$$
dp_{i,s1,s2}=\max_{s3}(dp_{i-1,s2,s3}+cnt_{s1})
$$
其中，$s3$ 表示 $i-2$ 行的状态，$cnt_{s}$ 表示状态 $s$ 中 $1$ 的个数（即摆放数）。
然后约束条件与上面两题一样，只是多了枚举第 $i-2$ 行的状态，照着做即可。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e3+10;
int n,m;
int mp[maxn];
int dp[105][maxn][maxn];
//dp[i][s1][s2]表示第i行状态为s1,第i-1行状态为s2的最大摆放数
struct node{
int s,cnt;
}zt[maxn];
int tot;
int get(int x){
int cnt=0;
while(x){
if(x%2) cnt++;
x/=2;
}
return cnt;
}
int ans;
void init(){
for(int i=0;i<(1<<m);i++){
if((i&(i<<1))||(i&(i<<2))) continue;
zt[++tot].s=i; zt[tot].cnt=get(i);
if(!((~mp[1])&i)) dp[1][tot][1]=zt[tot].cnt;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
if(ch=='P') mp[i]+=(1<<(m-j));
}
}
init();
for(int i=2;i<=n;i++){//枚举行
for(int s1=1;s1<=tot;s1++){//枚举第i行的状态
if((~mp[i])&zt[s1].s) continue;
for(int s2=1;s2<=tot;s2++){//枚举第i-1行的状态
if((~mp[i-1])&zt[s2].s) continue;
if(zt[s1].s&zt[s2].s) continue;
for(int s3=1;s3<=tot;s3++){//枚举第i-2行的状态
if((~mp[i-2])&zt[s3].s) continue;
if((zt[s1].s&zt[s3].s)||(zt[s2].s&zt[s3].s)) continue;
dp[i][s1][s2]=max(dp[i][s1][s2],dp[i-1][s2][s3]+zt[s1].cnt);
}
}
}
}
for(int s1=1;s1<=tot;s1++){
for(int s2=1;s2<=tot;s2++) ans=max(ans,dp[n][s1][s2]);
}
cout<<ans;
return 0;
}
```
:::
## 练习题目
1. [[蓝桥杯 2021 省 AB2] 国际象棋](https://www.luogu.com.cn/problem/P8756)
# 2. 集合式状压
这类问题的状态直接对应一个集合，二进制位上的 $1$ 或 $0$ 代表某个元素是否被选中，通常用于解决需要枚举元素子集的问题。
## 例题 1：[[POI 2004] PRZ](https://www.luogu.com.cn/problem/P5911)
:::info[题意]{open}
有 $n$ 个人过桥，桥最大承重 $W$。每个人 $i$ 有重量 $w_i$ 和过桥时间 $t_i$。
分批过桥，每批总重量 $\le W$。 批与批顺序进行。求所有人过完的最短总时间。
:::
当做集合式状压是不错的。很经典的枚举子集问题。
我们定义 $dp_s$ 表示选择了集合 $s$ 为一批的最短时间。
其中，$s$ 为二进制数，第 $i$ 位为 $1$ 表示选了第 $i$ 个人，否则不选。
那么 $dp_s$ 肯定是由 $s$ 的子集的反码转移过来的，即 $dp_{s\,\^{}\,s'}$，而代价是 $t_{s'}$，即状态为 $s'$ 时的通过时间。
则有
$$
dp_s=\min_{s'\in s}(dp_{s\oplus s'}+t_{s'})[w_{s'}\le W]
$$
预处理一下 $t$ 和 $w$ 即可。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int W,n;
int dp[maxn];
int t[maxn],w[maxn];
struct node{
int t,w;
}a[maxn];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>W>>n;
for(int i=1;i<=n;i++) cin>>a[i].t>>a[i].w;
for(int i=0;i<(1<<n);i++){
t[i]=w[i]=0;
dp[i]=LLONG_MAX;
for(int j=0;j<n;j++){
if((i>>j)&1){//选择第j个人
t[i]=max(t[i],a[j+1].t);//+1是因为a数组的下标是从1开始的
w[i]+=a[j+1].w;
}
}
}
dp[0]=0;
for(int i=0;i<(1<<n);i++){//枚举状态
for(int j=i;j;j=(j-1)&i){//枚举子集
if(w[j]>W) continue;
dp[i]=min(dp[i],dp[j]+t[i^j]);
}
}
cout<<dp[(1<<n)-1];
return 0;
}
```
:::
## 例题 2：[售货员的难题](https://www.luogu.com.cn/problem/P1171)
:::info[题意]{open}
给定 $n$ 个村庄，其中 $1$ 号为商店所在村庄。售货员从 $1$ 出发，恰好经过每个村庄一次，最后返回 $1$。
已知从村庄 $i$ 到村庄 $j$ 的单向路程为 $s_{i,j}$（$i, j \in [1, n]$）。求满足条件的最短总路程。
:::
TSP 问题模板。
我们定义 $dp_{s,i}$ 表示走完了点集 $s$ 后，最后停留在 $i$ 点的最短路程。
则有
$$
dp_{s,i}=\min_j(dp_{s\oplus 2^{i-1},j}+dis_{j,i})
$$
其中 $dis_{i,j}$ 表示从节点 $i$ 到 $j$ 的路程，$s\oplus2^{i-1}$ 即将 $s$ 的第 $i-1$ 位变为 $0$，表示不经过节点 $i$。
可以理解为寻找中间节点 $j$，使得路径更短。
也没有其他约束，那么我们就做完了。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=3e6+10;
int n,dis[25][25];
int dp[maxn][25];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int w;
cin>>w;
dis[i][j]=w;
}
}
for(int s=0;s<(1<<n);s++){
for(int i=1;i<=n;i++){
if(s&(1<<(i-1))){//状态s中经过城市i
if(s==1<<(i-1)) dp[s][i]=dis[1][i];
//状态s只经过i，最短自然是从起点到i
else{
dp[s][i]=LLONG_MAX;
for(int j=1;j<=n;j++){
if(j!=i&&(s&(1<<(j-1))))//不是i且经过
dp[s][i]=min(dp[s][i],dp[s^(1<<(i-1))][j]+dis[j][i]);
}
}
}
}
}
int ans=LLONG_MAX;
for(int i=1;i<=n;i++){
ans=min(ans,dp[(1<<n)-1][i]+dis[i][1]);
}
cout<<ans;
return 0;
}
```
:::
## 例题 3：[【模板】最小斯坦纳树](https://www.luogu.com.cn/problem/P6192)
:::info[题意]{open}
给定一个 $n$ 点 $m$ 边的无向连通图，边有正权。给定一个含 $k$ 个关键点的集合 $S$，求一个连通子图，包含 $S$ 中所有点，且边权和最小，输出最小边权和。
:::
容易发现，我们求的连通子图其实是一棵树。
:::info[证明]
若存在环，可选择割掉一条边，仍然满足连通，但边权更小。
:::
那么定义 $dp_{s,i}$ 表示以 $i$ 为根的树，包含集合 $s$ 中所有点的最小边权。
那么有两种情况。
1. 根的度为 $1$。
考虑找到一个与 $i$ 相邻且边权最小的节点 $j$，则有转移方程：
$$
dp_{s,i}=\min_j(dp_{s,j}+dis_{i,j})
$$
其中，$dis_{i,j}$ 表示 $i$ 到 $j$ 的边权。
2. 根的度大于 $1$。
考虑将 $i$ 的儿子分成两部分，则有：
$$
dp_{s,i}=\min_{s1\in s}(dp_{s1,i}+dp_{s\oplus s1,i})
$$
对于第一种转移，容易联想到最短路的松弛操作，做最短路即可。而对于第二种，枚举子集取最小即可。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1000+10;
int n,m,k;
bitset<maxn> vis;
int dp[1<<10][maxn];
int head[maxn],tot;
int p[maxn];
struct node{
int to,next,w;
}e[2*maxn];
void add(int u,int v,int w){
e[++tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
void spfa(int s){//spfa最短路
queue<int> q;
for(int i=1;i<=n;i++){
if(dp[s][i]!=0x3f3f3f3f) q.push(i),vis[i]=1;
}
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dp[s][v]>dp[s][u]+e[i].w){
dp[s][v]=dp[s][u]+e[i].w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w); add(v,u,w);
}
memset(dp,0x3f,sizeof(dp));//初始化
for(int i=1;i<=k;i++){
cin>>p[i];
dp[1<<(i-1)][p[i]]=0;//初始化
}
for(int s=1;s<(1<<k);s++){
for(int s1=s;s1;s1=(s1-1)&s){//枚举子集
for(int i=1;i<=n;i++){
dp[s][i]=min(dp[s][i],dp[s1][i]+dp[s^s1][i]);
}
}
spfa(s);
}
int ans=INT_MAX;
for(int i=1;i<=k;i++){
ans=min(ans,dp[(1<<k)-1][p[i]]);
}
cout<<ans;
return 0;
}
```
:::
由于用的是 SPFA，这里给出最坏时间复杂度是 $O(3^kn+2^knm)$。
## 练习题目
1. [灰化肥，会挥发](https://www.luogu.com.cn/problem/P4772)
2. [[NOIP 2016 提高组] 愤怒的小鸟](https://www.luogu.com.cn/problem/P2831)
3. [[NOIP 2017 提高组] 宝藏](https://www.luogu.com.cn/problem/P3959)
# 3. 基于连通性的状压
常被称作插头/轮廓线 DP。这类问题是记录轮廓线上各插头之间的连通性。其实大多数也在棋盘上。
## 例题：[【模板】插头 DP](https://www.luogu.com.cn/problem/P5056)
:::info[题意]{open}
给出 $n\times m$ 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法。
:::
~~我也要学这种东西吗？~~
已同步到[题解：P5056【模板】插头 DP](https://www.luogu.com.cn/article/1c1v1768)。
首先引入两个新的概念：
1. 轮廓线
即已处理和未处理各自的分割线。
\
（黄色的线就是轮廓线，红色的格子是正在处理的。）
2. 插头
插头具有方向性，若一个格子有插头，则代表这个格子与插头方向的格子连通。
对于插头的表示，我们使用括号表示法。
即对于轮廓线上的每一段，若存在插头且未被染色，则对所有与之连通的格子进行染色，且当前插头作为左边的插头，记为 $1$。若被染色，则与染上相同颜色的插头形成一对，当前插头为右边的插头，记为 $2$。若不存在插头，则记为 $0$。如下图：
\
（用序列表示的话即 $10212$，绿色的线表示一条回路。）
**Q：到第一个插头时不就把所有插头给染了吗？**
**A：注意到轮廓线是未处理和已处理格子的分割线，相当于一条边界，所以枚举到一个插头时，有的格子可能并未与其连通。**
我们可以用一个三进制数表示当前轮廓线的状态。
令 $dp_{i,j,s}$ 为处理到 $(i,j)$ 且轮廓线状态为 $s$ 的方案数。由于只需要用到上一个轮廓线，所以前两位可以滚掉。
这里有个插头 DP 的约束。
:::info[约束]{open}
从左往右的四个插头 $a,b,c,d$，如果 $a$ 与 $c$ 连通，则 $b$ 与 $d$ 不连通。
:::
这个约束后面有用。严谨的证明是不会的。
因为要形成回路，所以一个格子最多有两个插头。这里令右插头为 $p1$，上插头为 $p2$。
注：右插头在当前格子的左边，上插头在当前格子的右边。
开始讨论转移。
1. 当前格子为障碍。
那么只有 $p1=p2=0$ 时转移。
2. $p1,p2$ 都为 $0$。
此时，当前格子只能与下边和右边的格子（不为障碍）连通，那我们就只能新建左插头和上插头。
\
(蓝色表示新建的插头。)
3. $p1$ 和 $p2$ 中有一个为 $0$。
此时，我们可以选择建一个向下或向右的插头。
4. $p1=p2=1$。
那么直接把它们连起来即可。连起来后，我们会发现从当前格子向右的第一个右边的插头变成了左边的插头。
5. $p1=p2=2$。
同理，我们也把它们直接连起来。我们又会发现从当前格子向左的第一个左边的插头变成了右边的插头。
6. $p1=2,p2=1$。
此时直接连起来不会对**其他插头**产生影响。
7. $p1=1,p2=2$。
此时连起来会形成回路，由于上文提到的约束，这两个插头必定连通，所以必须是最后一个非障碍点才能连，答案也在此时统计。
由于状态是用三进制数存的，为了方便表示状态，可以用哈希存所有的状态，转移就从当前所有可能的状态扩展到下一位置即可。
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=15+10;
int n,m,d;
int ex,ey;
int ans,bin[maxn];;
bitset<maxn> vis[maxn];
unordered_map<int,int> dp[2];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
if(ch=='.') ex=i,ey=j,vis[i][j]=1;
}
}
bin[0]=1;
for(int i=1;i<=12;i++) bin[i]=bin[i-1]*3;
dp[d][0]=1;
for(int i=1;i<=n;i++){
unordered_map<int,int> tmp=dp[d];
dp[d].clear();
for(auto p:tmp) dp[d][p.first*3]=p.second;
for(int j=1;j<=m;j++){
d^=1; dp[d].clear();
for(auto p:dp[d^1]){
int s=p.first,cnt=p.second;//s表示状态,cnt表示方案数
int p1=s/bin[j-1]%3,p2=s/bin[j]%3;//p1是右插头,p2是上插头
if(!vis[i][j]){
if(!p1&&!p2) dp[d][s]+=cnt;
}
else if(!p1&&!p2){
if(vis[i][j+1]&&vis[i+1][j]) dp[d][s+bin[j-1]+2*bin[j]]+=cnt;
}
else if(!p1&&p2){
if(vis[i][j+1]) dp[d][s]+=cnt;
if(vis[i+1][j]) dp[d][s-p2*bin[j]+p2*bin[j-1]]+=cnt;
}
else if(p1&&!p2){
if(vis[i][j+1]) dp[d][s-p1*bin[j-1]+p1*bin[j]]+=cnt;
if(vis[i+1][j]) dp[d][s]+=cnt;
}
else if(p1==1&&p2==1){
int rb=1;
for(int l=j+1;l<=m;l++){//括号匹配
if(s/bin[l]%3==1) rb++;
else if(s/bin[l]%3==2) rb--;
if(!rb){
dp[d][s-bin[j-1]-bin[j]-bin[l]]+=cnt;
break;
}
}
}
else if(p1==2&&p2==2){
int lb=1;
for(int l=j-2;l>=0;l--){
if(s/bin[l]%3==1) lb--;
else if(s/bin[l]%3==2) lb++;
if(!lb){
dp[d][s-2*bin[j-1]-2*bin[j]+bin[l]]+=cnt;
break;
}
}
}
else if(p1==2&&p2==1) dp[d][s-2*bin[j-1]-bin[j]]+=cnt;
else if(i==ex&&j==ey) ans+=cnt;//统计答案
}
}
}
cout<<ans;
return 0;
}
```
:::
## 练习题目
1. [[HNOI2007] 神奇游乐园](https://www.luogu.com.cn/problem/P3190)
2. [Eat the Trees](https://www.luogu.com.cn/problem/P5074)
3. [[Code+#3] 白金元首与莫斯科](https://www.luogu.com.cn/problem/P4262)
4. [[JLOI2009] 神秘的生物](https://www.luogu.com.cn/problem/P3886)
# 参考文献
1. [OrangeRED - 题解：P6192 【模板】最小斯坦纳树](https://www.luogu.com.cn/article/ohr4p159)
2. [Jsxts_ - 题解 P5056](https://www.luogu.com.cn/article/00qtghqr)