题解：P17132 [ICPC 2025 Shanghai R] Yet another permutation problem
lailai0916
·
·
题解
题意简述
给定一个排列。可以继续切分当前各段，或交换某一段的最小值和最大值。求最终不同排列的数量，答案对 998244353 取模。
解题思路
把操作过程看成一棵分裂树。每个结点表示一个当前区间，结点上的交换发生在继续切分之前。
若一次切分没有分开当前最小值和最大值，这次交换可以下移到包含两者的子区间。因此，只需保留在第一次分开两极值前进行的交换。
祖先操作对区间 [l,r] 的相对大小关系仅有 3 种影响：
第二类状态的最小值和最大值，分别位于原次小值和原最小值处。第三类则分别位于原最大值和原次大值处。因此，预处理每个原区间的前两小值和前两大值位置，即可得到所有状态的两极值位置。
对当前状态的输入排列 b 和某个可达排列 c，考察位置 k。若两者在 [l,k] 上的值集相同，就称 k 为公共切分点。
沿所有公共切分点切开。所得各块没有内部公共切分点，且这种分解唯一。
设 f_{l,r,p} 表示没有内部公共切分点的方案数，g_{l,r,p} 表示全部方案数。
记当前状态限制到切分点 $k$ 两侧后，左右区间的类型为 $x_k,y_k$。枚举第一个公共切分点，得到：
$$
g_{l,r,p}=f_{l,r,p}+\sum_{k=l}^{r-1}f_{l,k,x_k}g_{k+1,r,y_k}
$$
令 $e_0,e_1$ 分别为当前最大值和最小值的位置。同理：
$$
h_{l,r,p,q}=f_{l,r,p}+\sum_{k=e_q}^{r-1}f_{l,k,x_k}g_{k+1,r,y_k}
$$
然后计算 $f$。设当前状态为 $b$，其最小值、最大值的位置为 $u,v$，交换两者后得到 $b'$。极小方案必须先交换两者，否则第一次切分本身就是公共切分点。
对任意位置 $k$，若 $k$ 不在 $\min(u,v)\sim\max(u,v)-1$ 内，则 $b$ 与 $b'$ 的前缀值集相同。因此，最终排列与 $b'$ 的公共切分点必须全部位于该范围内。
交换后令两极值在位置 $t$ 首次分开，此后没有元素能跨过 $t$。若 $u<v$，则 $k<t$ 时前缀不包含原最小值，$k\ge t$ 时前缀包含原最大值。两者均与 $b$ 的对应前缀值集不同，$u>v$ 时同理。只需限制相对于 $b'$ 的公共切分点均在两者之间。结合上述屏障，最终排列相对于 $b$ 就没有公共切分点。
枚举交换后的最后一个公共切分点 $k$。右侧必须是一个极小块，左侧不能在较早的极值位置左边切开。若 $u<v$，较早位置在交换后是最大值，取 $q=0$；否则取 $q=1$。设交换后两侧的类型为 $x'_k,y'_k$，则：
$$
f_{l,r,p}=\sum_{k=\min(u,v)}^{\max(u,v)-1}h_{l,k,x'_k,q}f_{k+1,r,y'_k}
$$
限制某个状态到子区间后，其类型可以在 $O(1)$ 时间内确定。若子区间包含强制放入的最小值，当前最小值就在该处。否则，若强制最大值替换了原最小值，当前最小值变为原次小值；其余情况仍取原最小值。比较该位置与原最小值、原次小值的位置，即可区分 $3$ 类状态。
长度为 $1$ 时，三类状态等价，所有 $f,g,h$ 均为 $1$。按照区间长度递增转移。
预处理复杂度为 $O(n^2)$。动态规划复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。
## 正确性证明
任意操作序列都能表示为分裂树。一个区间在第一次切分前，对自身两极值的多次交换只需保留奇偶性。若切分没有分开两极值，两者仍是同一子区间的两极值，所以该交换可以下移。重复处理后，每次保留的交换都会紧接着分开它交换的两极值。若操作在交换后直接结束，也可以补上不改变排列的切分。
由此对分裂树归纳。一个子区间若没有接收祖先交换的元素，则属于状态 $0$。若它接收了父区间最大值，就失去自身最小值，且新元素大于区间中所有原元素，属于状态 $1$。接收父区间最小值时同理，属于状态 $2$。因此，三类状态覆盖所有递归情况。
若最终排列存在公共切分点，该点两侧的值集均未发生净交换。跨过该点的最外层交换若被分开，其一个极值会永久留在另一侧，无法恢复原值集。
因此，这类交换只能继续下移，最终完全落在切分点一侧。两侧操作可以独立安排。
沿第一个公共切分点分解时，左侧必为极小块，右侧可以任意选择。因此，$g$ 的转移无重无漏。增加切分点的位置下界，便得到 $h$ 的转移。
再考虑没有公共切分点的方案。记交换前后的状态分别为 $b,b'$。根区间若不先交换，第一次切分就是公共切分点，因此必须先交换两极值。两极值随后第一次分到不同子区间。该切口两侧的值集不再改变，所以它一定是最终排列与 $b'$ 的公共切分点。
设两极值的位置为 $u,v$，记其第一次分开的切口为 $t$。再记 $I=[\min(u,v),\max(u,v))$。在 $I$ 外，$b$ 与 $b'$ 的前缀值集相同。最终排列与 $b'$ 在这些位置不能相同。否则，该位置也是它与 $b$ 的公共切分点。
若 $u<v$，则 $k<t$ 时原最小值始终在前缀外。$t\le k<v$ 时原最大值始终在前缀内。两者均不同于 $b$ 的前缀值集。$u>v$ 时交换最小值与最大值的角色即可。因此，该范围内也不会产生相对于 $b$ 的公共切分点。
取交换后的最后一个公共切分点。其右侧没有更多公共切分点，恰为 $f$ 统计的极小块。左侧的其余切分点不能越过较早的极值位置，恰由对应方向的 $h$ 统计。
反过来，$f$ 转移中的任一组合都先交换两极值。任选一个公共切分点，便可在该处将两者分开。相对于 $b'$ 的所有公共切分点都在两者之间。因此，范围外不会产生相对于 $b$ 的公共切分点。两极值分开后的屏障又排除了范围内的公共切分点。故 $f$ 的转移也无重无漏。
三类转移覆盖全部状态，且每次只依赖更短区间。结合长度为 $1$ 的初值，归纳可得 $g_{1,n,0}$ 正是所求不同排列数。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128_t;
const int N=505;
const int mod=998244353;
int a[N];
int f[N][N][3];
int g[N][N][3];
int h[N][N][3][2];
int mn[N][N],mn2[N][N],mx[N][N],mx2[N][N];
int state(int l,int r,int hi,int lo)
{
if(l==r)return 0;
int p=mn[l][r];
if(l<=lo&&lo<=r)p=lo;
else if(l<=hi&&hi<=r&&mn[l][r]==hi)p=mn2[l][r];
if(p==mn[l][r])return 0;
if(p==mn2[l][r])return 1;
return 2;
}
void calc(int l,int r,int p)
{
int hi;
int lo;
if(p==0)
{
hi=mx[l][r];
lo=mn[l][r];
}
else if(p==1)
{
hi=mn[l][r];
lo=mn2[l][r];
}
else
{
hi=mx2[l][r];
lo=mx[l][r];
}
int q=hi<lo;
i128 res=0;
for(int i=min(hi,lo);i<max(hi,lo);i++)
{
int x=state(l,i,lo,hi);
int y=state(i+1,r,lo,hi);
res+=(ll)h[l][i][x][q]*f[i+1][r][y];
}
f[l][r][p]=res%mod;
res=f[l][r][p];
i128 lef=res;
i128 rig=res;
for(int i=l;i<r;i++)
{
int x=state(l,i,hi,lo);
int y=state(i+1,r,hi,lo);
ll v=(ll)f[l][i][x]*g[i+1][r][y];
res+=v;
if(i>=hi)lef+=v;
if(i>=lo)rig+=v;
}
g[l][r][p]=res%mod;
h[l][r][p][0]=lef%mod;
h[l][r][p][1]=rig%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
int p=i;
int q=i;
int x=i;
int y=i;
for(int j=i;j<=n;j++)
{
if(j>i)
{
if(a[j]<a[p])
{
q=p;
p=j;
}
else if(q==p||a[j]<a[q])q=j;
if(a[j]>a[x])
{
y=x;
x=j;
}
else if(y==x||a[j]>a[y])y=j;
}
mn[i][j]=p;
mn2[i][j]=q;
mx[i][j]=x;
mx2[i][j]=y;
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<3;j++)
{
f[i][i][j]=1;
g[i][i][j]=1;
h[i][i][j][0]=1;
h[i][i][j][1]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=1;j+i-1<=n;j++)
{
for(int k=0;k<3;k++)calc(j,j+i-1,k);
}
}
cout<<g[1][n][0]<<'\n';
return 0;
}
```