一类基于笛卡尔树的排列计数DP
command_block
2021-10-21 22:00:06
# [P5999 [CEOI2016]kangaroo](https://www.luogu.com.cn/problem/P5999)
**题意** ： 有 $n$ 个草丛排成一排，编号 $1\sim n$ 。
有一只袋鼠，从 $s$ 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 $t$。显然他会跳跃 $n-1$ 次。
为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。
求方案数模 $10^9+7$ 的结果。
$n\leq 2\times 10^3$ ，时限$\texttt{1s}$。
------------
按访问顺序把编号记下，得到排列 $P$ ，则约束为 ：
- $P_1=s,P_n=t$。
- 对于 $1<i<n$ ，$P_{i-1}<P_i>P_{i+1}$ 或 $P_{i-1}>P_i<P_{i+1}$ ，排列形如“波浪”。
对于排列计数 DP 问题，一种经典的手段是从小到大插入元素，但此题中不合法的序列可能在插入后变得合法，故不能采用插入法。
从小到大考虑元素，观察排列的表现。已加入的元素会形成若干个连续段，这些连续段内部一定是合法的。
设 $dp[i][j]$ 表示考虑了数 $1\sim i$ ，形成 $j$ 个连续段（考虑的是以连续段为元素的有序序列，不考虑中间的空位有几个等等），内部合法，段的左右都是波谷（不包括 $s,t$），的方案数。
插入 $i$ 时，讨论如下：
- 当 $i\neq s,t$ 时
- 可以作为新的一段插入。若 $i>s$ （$s$ 已经插了）不能插在首，若 $i>t$ 不能插在尾。
记 $c=[i>s]+[i>t]$ ，$f_{i,j+1}\leftarrow (j+1-c)\times f_{i-1,j}$
- 可以合并两段。
此时 $i$ 比已有的任一个数都要大，必然可以合成并作为波峰。
$f_{i,j-1}\leftarrow (j-1)\times f_{i-1,j}$
- 当 $i=s$ 时
- 作为新的一段插在最前面 ：$f_{i,j+1}\leftarrow f_{i-1,j}$
- 放在最前面的段的前面 ：$f_{i,j}\leftarrow f_{i-1,j}$
（$i=t$ 时类似）
可以发现，每种合法的排列都恰会被计数一次。
首先显然被计数的排列都是合法的，只需证每种合法排列恰只有一种计数方式。
对于给定的合法排列 $P$ ，从小到大考虑其中元素，维护两侧为波谷的连续段，每次插入可以得到对应的操作。
不难发现这类似于**水淹笛卡尔树**并维护森林，不同排列对应不同的笛卡尔树，自然，水淹森林的过程也就不同。
复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 2050
using namespace std;
const int mod=1000000007;
int n,s,t,f[MaxN][MaxN];
int main()
{
scanf("%d%d%d",&n,&s,&t);
f[0][0]=1;
for (int i=1;i<=n;i++)
if (i==s||i==t){
for (int j=1;j<=i;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
}else {
int c=(i>s)+(i>t);
for (int j=1;j<=i;j++)
f[i][j]=(1ll*j*f[i-1][j+1]+1ll*(j-c)*f[i-1][j-1])%mod;
}
printf("%d",f[n][1]);
return 0;
}
```
# [CF704B Ant Man](https://www.luogu.com.cn/problem/CF704B)
**题意** ： 有 $n$ 个元素，第 $i$ 个元素有五个参数$x_i,a_i,b_i,c_i,d_i$。
- 求出一个 $1 \sim n$ 的排列 $P$，满足 $P_1 = s, P_n = e$，同时最小化这个排列的权值。
- 排列 $P$ 的权值为 $\sum_{i=1}^{n-1} f(P_i, P_{i+1})$，其中 $f(i,j)$ 的值有两种情况：
- 若 $i>j$，则 $f(i,j) = x_i - x_j + c_i + b_j$。
- 若 $i<j$，则 $f(i,j) = x_j - x_i + d_i + a_j$。
$n\leq 5\times 10^3$ ，时限$\texttt{4s}$。
------------
令 $a_i\leftarrow a_i+x_i,\ b_i\leftarrow b_i-x_i,\ c_i\leftarrow c_i+x_i,\ d_i\leftarrow d_i-x_i$ ，则有
$$f(i,j)=\begin{cases}c_i+b_j&(i>j)\\d_i+a_j&(i<j)\end{cases}$$
设 $dp_{i,j}$ 表示考虑了前 $i$ 个数，形成 $j$ 个连续段的方案数。
加入 $i$ 时，讨论 $i$ 两侧贡献的四种情况，计算关于 $a_i,b_i,c_i,d_i$ 的贡献。
- $i\neq s,e$
- 两侧都比自己大：自成一段。注意若 $i>s,e，j=1$ 则无法转移，此时找不到空位加入新的段。
$f_{i,j+1}\leftarrow f_{i-1,j}+b_i+d_i$
- 两侧都比自己小：合并两段。
$f_{i,j-1}\leftarrow f_{i-1,j}+a_i+c_i$
- 左小右大：贴在一段右侧。注意若 $i>e,j=1$ 则无法转移。
$f_{i,j-1}\leftarrow f_{i-1,j}+a_i+d_i$
- 左大右小：贴在一段左侧。注意若 $i>s,j=1$ 则无法转移。
$f_{i,j-1}\leftarrow f_{i-1,j}+b_i+c_i$
- $i=s$ 或 $i=e$
就只需考虑贴最左侧和贴最右侧的情况，和上面类似。
复杂度 $O(n^2)$ 。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 5050
using namespace std;
const ll INF=1ll<<60;
#define chkmin(a,b) a=min(a,b)
int n,s,e,x[MaxN],a[MaxN],b[MaxN],c[MaxN],d[MaxN];
ll f[2][MaxN];
int main()
{
scanf("%d%d%d",&n,&s,&e);
for (int i=1;i<=n;i++)scanf("%d",&x[i]);
for (int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=x[i];}
for (int i=1;i<=n;i++){scanf("%d",&b[i]);b[i]-=x[i];}
for (int i=1;i<=n;i++){scanf("%d",&c[i]);c[i]+=x[i];}
for (int i=1;i<=n;i++){scanf("%d",&d[i]);d[i]-=x[i];}
for (int i=1;i<=n;i++)f[01][i]=INF;
for (int i=1,cur=0;i<=n;i++){
cur^=1;
for (int j=0;j<=i;j++)f[cur][j]=INF;
if (i!=s&&i!=e){
for (int j=0;j<i;j++){
if (i<max(s,e)||j>1)chkmin(f[cur][j+1],f[cur^1][j]+b[i]+d[i]);
if (j>1)chkmin(f[cur][j-1],f[cur^1][j]+a[i]+c[i]);
if ((i<e||j>1)&&j>0)chkmin(f[cur][j],f[cur^1][j]+a[i]+d[i]);
if ((i<s||j>1)&&j>0)chkmin(f[cur][j],f[cur^1][j]+b[i]+c[i]);
}
}else if (i==s){
for (int j=0;j<i;j++){
chkmin(f[cur][j+1],f[cur^1][j]+d[i]);
if (j>0)chkmin(f[cur][j],f[cur^1][j]+c[i]);
}
}else if (i==e){
for (int j=0;j<i;j++){
chkmin(f[cur][j+1],f[cur^1][j]+b[i]);
if (j>0)chkmin(f[cur][j],f[cur^1][j]+a[i]);
}
}
}printf("%lld",f[n&1][1]);
return 0;
}
```
# [Loj#2743. 「JOI Open 2016」摩天大楼](https://loj.ac/p/2743)
**题意** 对于 $A_{1\sim n}$ 的排列 $P$ ，定义其“波动度”为：
$$\sum\limits_{i=1}^{n-1}|P_i-P_{i+1}|$$
求波动度 $\leq c$ 的排列数目。答案对 $10^9+7$ 取模。
$n\leq 100,c\leq 1000$ ，时限$\texttt{2s}$。
------------
显然绝对值可以拆开，变成讨论相邻两个数的大小关系。但这样贡献可能有负数，求和不单调，复杂度较差。
一个使得贡献单调的技巧是**分层**。将 $A$ 排序，观察 $A_i-A_{i-1}$ 的贡献系数，是满足一个 $\leq A_{i-1}$ ，另一个 $\geq A_i$ 的对子 $(P_j,P_{j+1})$ 的个数。
每次插入 $A_i$ 时，计算 $A_i-A_{i-1}$ 的贡献系数（显然为正）。这样的贡献是单调不降的，于是可以应用 $c$ 的限制。
记 $dp_{i,j,k,0\sim 2}$ 表示前 $i$ 个数，形成了 $j$ 个连续段，目前贡献和为 $k$ ，选择了 $0\sim 2$ 个边界元素的方案数。
对于新形成的边，显然有贡献，对于未形成的边和已形成的边则无贡献。
讨论有五类：自成一段，自成一边界段，贴在段的一侧，贴在段的一侧并作为边界，连接两个段。
转移见代码。
最后 $\sum_{k\leq c} dp_{n,1,k,2}$ 就是答案。
将 $i$ 滚动。时间复杂度 $O(n^2c)$ ，空间复杂度 $O(nc)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 105
#define MaxK 1050
using namespace std;
const int mod=1000000007;
#define add(a,b) a=(a+b)%mod
int n,c,a[MaxN],f[2][MaxN][MaxK][3];
int main()
{
scanf("%d%d",&n,&c);
if (n==1){puts("1");return 0;}
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
f[1][1][0][0]=1;f[1][1][0][1]=2;
for (int i=2,cur=1;i<=n;i++){
cur^=1;
memset(f[cur],0,sizeof(f)>>1);
int det=a[i]-a[i-1];
for (int j=1;j<i;j++)
for (int k=0;k<=c;k++)
for (int o=0;o<=2;o++)
if (f[cur^1][j][k][o]){
int buf=f[cur^1][j][k][o],k2=k+(2*j-o)*det;
if (k2>c)continue;
add(f[cur][j+1][k2][o],1ll*(j+1-o)*buf);//自成一中段
if (o<2)add(f[cur][j+1][k2][o+1],1ll*(2-o)*buf);//自成一边段
if (j>=2)add(f[cur][j-1][k2][o],1ll*(j-1)*buf);//连两段
add(f[cur][j][k2][o],1ll*(2*j-o)*buf);//贴
if (o<2)add(f[cur][j][k2][o+1],1ll*(2-o)*buf);//贴，并产生边段
}
}
int ans=0;
for (int k=0;k<=c;k++)
add(ans,f[n&1][1][k][2]);
printf("%d",ans);
return 0;
}
```
# [CF1515E Phoenix and Computers](https://www.luogu.com.cn/problem/CF1515E)
**题意** ： 给定 $n$ ，有 $n$ 个电脑排成一排。
初始时所有电脑都关机，你要**按某种顺序**手动开电脑，使得最终所有电脑都被开启位置。
若某电脑两侧的电脑都开机，这台电脑会立刻自动开机。不能开一个已经开了的电脑。
将手动开的电脑编号依次记下，求有多少种可能的编号序列。
答案对给定的质数 $mod$ 取模。
$n\leq 400$ ，时限$\texttt{3s}$。
------------
设 $f_{i,j}$ 表示已开机（包括手动和自动） $i$ 台，形成了 $j$ 个连续段，且钦定连续段间距离 $>1$ 的情况。
对于 $f_{i,j}$ ，新开一台，可能的转移如下：
- 新增一段 ： $f_{i,j}\times (j+1)\rightarrow f_{i+1,j+1}$
- 合并两段 ：
- 两侧紧贴：不合法，这样早就会触发自动开机。
- 一侧紧贴，另一侧空一位自动开机： $f_{i,j}\times 2(j-1)\rightarrow f_{i+2,j-1}$
- 两侧各空一位自动开机： $f_{i,j}\times (j-1)\rightarrow f_{i+3,j-1}$
- 贴在某段一侧 ：
- 紧贴： $f_{i,j}\times 2j\rightarrow f_{i+1,j}$
- 空一位自动开机： $f_{i,j}\times 2j\rightarrow f_{i+2,j}$
最终 $f_{n,1}$ 是答案。
复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 405
using namespace std;
#define add(a,b) a=(a+b)%mod
int n,mod,a[MaxN],f[MaxN][MaxN];
int main()
{
scanf("%d%d",&n,&mod);
f[0][0]=1;
for (int i=0;i<n;i++){
for (int j=0;j<=i;j++){
add(f[i+1][j+1],1ll*f[i][j]*(j+1));
if (j>=2){
add(f[i+2][j-1],1ll*f[i][j]*2*(j-1));
add(f[i+3][j-1],1ll*f[i][j]*(j-1));
}
if (j>=1){
add(f[i+1][j],1ll*f[i][j]*2*j);
add(f[i+2][j],1ll*f[i][j]*2*j);
}
}
}printf("%d",f[n][1]);
return 0;
}
```