浅谈一类带限制的排列计数问题

可能更洛谷的阅读体验

0.前言

2025.6.11 UPD：更新了枚举最大值转移 DP，删除了杂项，大幅重写文章。

引用蓝书的一句话：

在求解计数类动态规划问题时，通常要找到一个 “基准点”，围绕这个基准点构造一个不可划分的整体，以避免子问题之间的重叠。

在解决排列限制类问题，我们关键就是找到一种生成顺序，使得生成部分不需要逐个记录，而只需要少量的状态即可记录。

1. 顺序扫描线与插入法

当遇到相邻项限制的排列计数问题，可能第一次做脑子就一头蒙，因为如果直接算排列会算重，想容斥但是限制不好容斥，于是就没招数了 www。

事实上，我们可以把这个长为$n$ 的排列元素都拿出来，让后我们可以一个元素一个元素类似于插入的方式进行 DP 的转移，通过这种一个一个插入的方式我们就能打破题目中转移限制的壕沟。事实上，插入法，实际上就是顺序扫描线，通过逐个插入满足特殊的限制。 有的时候我们一个一个元素的转移，而有的时候只考虑关键点，其他元素利用组合数进行转移。

而在插入过程中，因为我们要考虑相邻项的限制条件。为了方便转移，我们在插入的同时也许要维护插入项的相对数值或者是绝对数值，通常来说就是在 DP 数组内加上一个状态来维护当前项的相对大小或绝对大小，我们按照维护的状态和扫描顺序归结为下类 4 种 DP：

	绝对数值（预定）	相对数值（插入）
下表遍历	从左往右逐一确定值	从左往右逐一确定排名
值域遍历	从小到大逐一确定位置	从小到大注意插入排列

我们利用插入法，一个一个元素来看，将每一个元素作为基准点，并利用基准点，围绕限制构造一个不可划分的整体，通过这样，我们就能够避免子问题的重叠。

一般而言，当我们限制方向和 DP 转移方向一致的时候，我们可以考虑记录绝对数值（因为可以优化），反之考虑插入法。

接下来，我们一个一个来看每一类问题：

从左往右逐一确定值

这种做法显而易见的弊端就是容易出现重复元素，考虑状压记录某个值是否出现过，通常会出现容斥原理来进行优化，在第四章我们提到。

从小到大逐一确定位置

同上利用状压记录是否填写过，优化状态，我做的题太少还没有见到这一类，有的话欢迎在评论区分享 OvO。

从左往右逐一确定排名

这一类题是偏多的。

AT_dp_t

对排列的 DP，可以选择按照序列顺序或值域顺序确定具体数值或相对数值。

这个题给定的是相邻项的限制，直接做容斥不太好做，我们不妨考虑上面的思想，我们考虑插入法。

我们考虑 DP 需要维护什么，首先因为我们是一个扫描线的遍历方式，所以我们的 DP 数组需要$i$ 一个维护来维护当前我们扫到当前位置的答案。我们考虑从小到大填写。

我们很容易得到一个状态$f(i,j)$ 表示当前扫到第$i$ 个数，当前填写的数是$j$ 的方案数。

然而实际上你仔细考虑发现算重的条件太多了，因为限制关系只关心大小而并非实际的数据。我们考虑我们需要什么，我们需要统计的排列，相邻项的限制只关心其相对大小关系，而与其具体大小无关，所以我们应当采用维护值的排名。

故，设$f(i,j)$ 表示我们当前扫到第$i$ 个位置，当前项填写数在已经填写的数里面的相对大小是$j$ 的总方案数。

转移是显然的，我们考虑从$f(i,<j)$ 和$f(i,>j)$ 转移过来，这样的时间复杂度是$O(n^3)$，不妨考虑前缀和优化，时间复杂度$O(n^2)$。

等会，如果状态这么设置，那初始化$f(1,1)$ 不应该是$n$ 吗，为啥题解设置的都是$1$？实质上是没有理解为什么我们要设置相对大小而不是绝对大小

我们第一个加入的数可以随便填写，而后面扫描的时候插入是会限制的，所以我们不能考虑这个数的值不然，我们考虑排名，在不断往后插的过程，值是动态的，每插入一个数，前$i$ 个数是$[1,i]$ 的排列所构成的。不断扫描到$n$，这个时候我们的答案的排列就是原来长为$n$ 的排列。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3520,MOD=1e9+7;
int f[MN][MN],sum[MN][MN],n;
string s;

signed main(){
    cin>>n>>s;
    s=' '+s;
    f[1][1]=1;
    for(int i=1;i<=n;i++){
        sum[1][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(s[i-1]=='<') f[i][j]=sum[i-1][j-1]%MOD;
            else if(s[i-1]=='>') f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+MOD)%MOD;
            sum[i][j]=(sum[i][j-1]+f[i][j])%MOD;
        }
    }
    cout<<sum[n][n];
    return 0;
}

abc282g

不难注意到题目要求限制就是同大或者同小，没有要求特定值的限制。对于本题，我们按照序列顺序确定相对数值

但是这里的答案要求维护限制的贡献，如果我们不维护发现是无法转移的。我们不妨考虑把这个贡献设进状态。

故$f(i,j,k,l)$ 表示扫到第$i$ 个元素，$a_i$ 在$A$ 中的排名为$j$，$B_i$ 在$B$ 中的排名为$k$，有$l$ 个位置满足限制即可。

转移仍和上面差不太多，小于大于转移即可，注意到还要用二维前缀和，时间复杂度$O(n^{3} k)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=101;
int n,K,MOD,f[MN][MN][MN][MN],sum[MN][MN][MN][MN];

signed main(){
    cin>>n>>K>>MOD;
    f[1][0][1][1]=sum[1][0][1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=K;j++){
            for(int k=1;k<=i;k++){
                for(int p=1;p<=i;p++){
                    f[i][j][k][p]=((f[i][j][k][p]+sum[i-1][j-1][k-1][p-1])%MOD+MOD)%MOD;
                    f[i][j][k][p]=((f[i][j][k][p]+sum[i-1][j][k-1][i-1]-sum[i-1][j][k-1][p-1])%MOD+MOD)%MOD;
                    f[i][j][k][p]=((f[i][j][k][p]+sum[i-1][j][i-1][p-1]-sum[i-1][j][k-1][p-1])%MOD+MOD)%MOD;
                    f[i][j][k][p]=((f[i][j][k][p]+sum[i-1][j-1][i-1][i-1]-sum[i-1][j-1][k-1][i-1]-sum[i-1][j-1][i-1][p-1])%MOD+sum[i-1][j-1][k-1][p-1]%MOD+MOD)%MOD;
                    sum[i][j][k][p]=(((sum[i][j][k-1][p]+sum[i][j][k][p-1]-sum[i][j][k-1][p-1])%MOD+MOD)%MOD+f[i][j][k][p])%MOD;
                }
            }
        }
    }
    cout<<sum[n][K][n][n];
    return 0;
}

CF995F

等一会这不是排列吗？

我其实一开始只是想做关于排列，但是考虑到这一类思想在许多题目出现，选一些题目来见识见识。

“恰好” 一词很好，我们可以考虑转二项式反演，注意到分配的工资数很多，但实际上最多只能用$n$ 种。我们可以考虑记录相对大小关系。

我们不妨设$f(i,j)$ 表示以$i$ 为根的子树，节点$i$ 的权值相对大小是第$j$ 大的合法方案数，不难得出转移方程：

$$f(i,j)=\prod_{v\in son(i)} \sum\limits_{k=1}^j f(v,k)$$

不难前缀和优化，时间复杂度$O(n^2)$。

然而，注意到这个实际上是至多使用，因为我们可以重复分配同价值的工作，而在根节点$1$ 号点取道最大值。

我们令$g_i$ 表示用$[1,i]$ 的数填进去，恰好用$i$ 种权值的方案数，考虑二项式反演，那么容斥方程如下：

$$g_{i}=f(1,i)-\sum\limits_{j=1}^{i-1} \binom{i-1}{j-1} g_{j}$$

最终答案即为：

$$\sum\limits_{i=1}^{\min(n,d)} \binom{d}{i} g_{i}$$

时间复杂度$O(n^2)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=3000+15,MOD=1e9+7;
int n,d,sum1,sum2,g[MN][MN],jc[MN],inv[MN];
ll ans;
vector<int> adj[MN];

int ksm(ll a,int b){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret%MOD;
}

void init(){
    jc[0]=1;
    for(int i=1;i<MN;i++) jc[i]=1ll*jc[i-1]*i%MOD;
    inv[MN-1]=ksm(jc[MN-1],MOD-2);
    for(int i=MN-2;i>=0;i--){
        inv[i]=1ll*inv[i+1]*(i+1)%MOD;
    }
}

int getC(int a,int b){
    if(a<b) return 0;
    return 1ll*jc[a]*inv[b]%MOD*inv[a-b]%MOD;
}

void dfs(int u){
    for(int i=1;i<=n;i++){
        g[u][i]=1;
    }
    for(auto v:adj[u]){
        dfs(v);
        int sum=0;
        for(int i=1;i<=n;i++){
            sum=(sum+g[v][i])%MOD;
            g[u][i]=1ll*g[u][i]*sum%MOD;
        }
    }
}

signed main(){
    init();
    cin>>n>>d;
    for(int i=2;i<=n;i++){
        int v;
        cin>>v;
        adj[v].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        g[1][i]=(g[1][i]+g[1][i-1])%MOD;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            g[1][i]=(g[1][i]-1ll*g[1][j]*getC(i,j)%MOD+MOD)%MOD;
        }
    }
    sum1=sum2=1;
    for(int i=1;i<=n;i++){
        sum1=1ll*sum1*(d-i+1)%MOD;
        sum2=1ll*sum2*i%MOD;
        ans=(ans+1ll*sum1*ksm(sum2,MOD-2)%MOD*g[1][i]%MOD)%MOD;
    }
    cout<<ans%MOD;
    return 0;
}

从小到大逐一确定值

与确切的位置无关，与位置相对关系有关，在接下来的枚举最大值转移会介绍到，请读者一定要坚持啊啊啊。

2. 连续段DP

连续段利用的是插入法的思想。

连续段 DP 主要用来解决一类计数问题，不光是排列计数问题，这类问题通常的特点是，如果只考虑在序列的两端插入，问题将容易解决（或者说有更简便的状态记录方式），状态转移的过程可能和相邻已插入元素的具体信息相关。

我们可以依次插入每个元素，连续段 dp 的元素插入操作只会在连续段的两端进行。

连续段起手 DP 式子：$f_{i,j}$ 表示插入到第$i$ 个数，划分出$j$ 个连续段的方案数。

转移考虑：

• 当前元素新开一个连续段。
• 接在已有连通块的首或尾。
• 元素用于连接两个连续段。

连续段 dp 的方式是将其理解为建立笛卡尔树的过程。新开一个连通块就是新建叶子节点，合并就是把两颗子树合并为一颗并以当前节点为根，接在首/尾就是选一颗子树作为当前节点的儿子，这样当前节点只会有一个儿子。当然，这只是一种理解方式，请不要和下面枚举最大值转移搞混。

连续段 dp 之所以能够避免记录信息的问题，是因为元素的插入，连续段的合并等操作均在连续段的两端进行，而在这类题目中，这种策略能使得状态维护变得简单。

而对于连续段的定义，每个题都有不同的设计方案，接下来我们通过例题一道一道来体会连续段的设计。

CF1515E Phoenix and Computers

我们手玩样例，不难发现一种组合方案：“ABABA” 其中 “A” 代表手动开启，“B” 代表依赖两边来开启。而方案中我们也可以打破这种，例如 ：”ABABAA“。

不难发现这是一个类似于连续段的形式，不妨考虑连续段 DP，设$f(i,j)$ 表示插入到第$i$ 个数，划分出$j$ 个连续段的方案数。我们考虑分类讨论上面提到的 3 种情况：

1. 新建段：显然由$f[i-1][j-1]$ 转移过来，这个连续段可以里面随便找位置插进去，一共$j$ 个空。乘法原理即可。

$$f[i][j]=f[i-1][j-1]\times j$$

2. 合并段：两个情况，第一个是中间空 2 个格子，随便加上一个另一个就能配对。第二种就是中间空了三个格子，这种情况加入中间的那个就可以连起来了。

$$f[i][j]=f[i-1][j+1]\times 2 \times j$$

$$f[i][j]=f[i-3][j+1]\times j$$

3. 插段里：因为没有生成新的段，由$f[i-1][j]$ 转移过来，因为每一个段两端都可以加，直接乘上$j\times 2$ 即可。第二个就是隔一个加入，这样又会有一个自动生成，相当于加了 2 个。

$$f[i][j]=f[i-1][j]\times j \times 2$$

$$f[i][j]=f[i-2][j]\times 2 \times j$$

上面的情况结合起来即可，时间复杂度$O(n^2)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520;
int f[MN][MN],n,MOD;

signed main(){
    cin>>n>>MOD;
    f[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(j+1)%MOD)%MOD;
            f[i+1][j]=(f[i+1][j]+f[i][j]*2*j%MOD)%MOD;
            f[i+2][j]=(f[i+2][j]+f[i][j]*2*j%MOD)%MOD;
            if(j>=2){
                f[i+2][j-1]=(f[i+2][j-1]+f[i][j]*(j-1)%MOD*2%MOD)%MOD;
                f[i+3][j-1]=(f[i+3][j-1]+f[i][j]*(j-1)%MOD)%MOD;
            }
        }
    }
    cout<<f[n][1]<<'\n';
    return 0;
}

CEOI 2016kangaroo

有多少长为$n$ 的排列$p$ 使得$\forall i \in (1,n)$，$p_i$ 两边的数同时小于或大于$p_i$，且$p_1=s,p_n=t$。

还是这种特殊限制，我们不妨考虑插入法。

不难手玩样例发现连续段的形式：大小大小大小大小。

我们设状态：$f_{i,j}$ 表示插入到第$i$ 个数，划分出$j$ 个连续段的方案数。我们考虑从小到大插入。

1. 新建块：注意到后加入一定比$i$ 大，所以后面插入在$i$ 两边的数一定比$i$ 大，所以不用考虑新开一段与前面段的大小限制。但是我们要考虑$p_{1}$ 与$p_{n}$ 的限制，如果$i>s$ 不能，同理$i>t$，故转移为：$f[i][j]=f[i-1][j-1]\times (j-[i>s]-[i>t])$。
2. 插入块两端：如果有这种情况的话，那么后面一定会有一个$>i$ 的数接在$i$ 另一侧，但是这样的话这不就是合并成一个块了吗，与题意不符。
3. 合并块：转移是显然的和上面一样：$f[i][j]=f[i-1][j+1]\times j$。

时间复杂度$O(n^2)$，故代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e3+15,MOD=1e9+7;
int n,s,t,f[MN][MN];

signed main(){
    cin>>n>>s>>t;
    f[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i!=s&&i!=t){
                f[i][j]=((j*f[i-1][j+1])%MOD+f[i-1][j-1]*(j-(i>s)-(i>t))%MOD)%MOD;
            }
            else f[i][j]=(f[i-1][j]+f[i-1][j-1])%MOD;
        }
    }
    cout<<f[n][1];
    return 0;
}

接下来我们来看不同种类的连续段设计类型：

COCI 2021/2022 #2 Magneti

样例 3 解释提示的很明显了吧。

我们还是考虑插入法，先按照特定顺序插入，例如从小到大插，根据$r_i$ 排序。

注意到样例 3 的解释中，图示是一个连续段的形式，自己手模以一下发现确实是这样的。

考虑连续段 DP，但是这样设状态是不太对的，因为我们还有不相互吸引的条件，如果不设置一个空位状态的话是无法处理限制的，所以我们要多设置空位的状态。

即：设$f_{i,j,k}$ 表示到第$i$ 个位置，形成了$j$ 个连续段，空位使用了$k$ 个的方案数。

转移方法还是我们上面的分类讨论：

• 成新段：$f[i][j][k]=f[i-1][j-1][k-1]$。
• 接在段两端：$f[i][j][k]=f[i][j][k]+f[i-1][j][k-r_{i}]\times j \times 2$。
• 合并段：$f[i][j][k]=f[i-1][j+1][k-2]\times r_{i}+1]\times j \times (j+1)$。

最后统计答案考虑插板法，贡献为$f_{n,1,i}\times \binom{l-i+n}{n}$，时间复杂度$O(n^{2}l)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=55,ML=1e4+5,MOD=1e9+7;
int n,l,r[MN],f[MN][MN][ML],pw[ML],inv[ML];

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

void init(){
    pw[0]=1;
    for(int i=1;i<ML;i++) pw[i]=pw[i-1]*i%MOD;
    inv[ML-1]=ksm(pw[ML-1],MOD-2);
    for(int i=ML-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD;
}

int getC(int a,int b){
    if(a<b) return 0;
    return pw[a]*inv[b]%MOD*inv[a-b]%MOD;
}

signed main(){
    init();
    cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>r[i];
    }
    sort(r+1,r+1+n);
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<=l;k++){
                f[i][j][k]=f[i-1][j-1][k-1];
                if(k>=r[i]) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-r[i]]*2*j%MOD)%MOD;
                if(k>=2*r[i]-1){
                    f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-2*r[i]+1]*j%MOD*(j+1)%MOD)%MOD;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=l;i++){
        ans=(ans+f[n][1][i]*getC(l-i+n,n)%MOD)%MOD;
    }
    cout<<ans%MOD;
    return 0;
}

排列游戏

课上 yy 半天。

首先第一个不难发现的点，$f(p)=\frac{1}{2} \sum\limits |i-p_{i}|$，通过手模样例即可。

证明考虑首先每次操作代价如果为$x$，那么最多使得$w(p)=\sum\limits|i-p_{i}|$ 减少$2x$。并且总存在一种用$x$ 的方案使得将$w(p)$ 减少$2x$。

接下来有一个很经典的 Trick，我们考虑将$i\rightarrow p_i$ 连边，那么会出现如下奇妙的性质：

我们注意到， 每一个元素都构成了一个环，而且环内元素是可以相互置换的。总的来说会形成几个置换环，而对于置换环上的每个边$(u,v)$ 都有$|u-v|$ 的贡献。注意到这个置换环也是一个连续整段的性质，设$f(i,j,k)$ 表示已经插入到第$i$ 个数，当前形态的置换环（或者连续段）个数为$j$，贡献和为$k$ 的方案数。

考虑怎么转移。新插入有如下可能：

• 新开环，这个又分成是否连成自环两种。
• 把一个没有封口的置换环变成了一个完整的环。
• 直接接在某个还未封口的置换环的开头或结尾。
• 接在某个未封口的结尾和另一个的开头，合并。

这样的时间复杂度是$O(nm^2)$，加点至多把$i$ 相邻的至多两条边计入贡献。

我们可以把每条边的贡献进一步细化到值域上，如果当前$j$ 条边还没有接续，如果想要达成$j$ 个置换环，总权值至少为$2+4+\dots+2j=j^2$ 级别，开$\sqrt{m}$ 即可，时间复杂度$O(nm\sqrt{m})$。

双倍经验：ABC134F

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520,QM=80,MM=10005,MOD=1e9+7;
int T,n,m,now,inv2=(MOD+1)/2,f[2][MN][MM],ans[MN][MM],pw[MM],inv[MM];

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}

void initpw(){
    pw[0]=1;
    for(int i=1;i<MM;i++){
        pw[i]=pw[i-1]*i%MOD;
    }
    inv[MM-1]=ksm(pw[MM-1],MOD-2);
    for(int i=MM-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%MOD;
    }
}

int getC(int a,int b){
    if(a<b) return 0;
    return pw[a]*inv[b]%MOD*inv[a-b]%MOD;
}

int getpw(int x){
    if(x&1) return MOD-1;
    else return 1;
}

void dodp(){
    initpw();
    f[now][0][0]=1;
    for(int i=1;i<MN;i++){
        now^=1;
        for(int j=0;j<=min(i,QM);j++){
            for(int k=(j-1)*j;k<MM;k+=2){
                f[now][j][k]=0;
                if(j>0) f[now][j][k]=(f[now^1][j-1][k-2*(j-1)]+f[now][j][k]+MOD)%MOD;
                if(k>=2*j) f[now][j][k]=(f[now][j][k]+f[now^1][j][k-2*j]*(2*j+1)+MOD)%MOD;
                if(k>=2*(j+1)) f[now][j][k]=(f[now][j][k]+f[now^1][j+1][k-2*(j+1)]*(j+1)%MOD*(j+1)%MOD)%MOD;
            }
        }
        for(int j=0;j<MM;j++){
            if(j&1) continue;
            int k=j/2,ret=f[now][0][j];
            if(k<=i){
                (ret+=(getpw((i&1)+(k&1))*getC(i-1,k)))%=MOD;
            }
            ret=ret*inv2%MOD;
            ans[i][j]=((j>0?ans[i][j-2]:0)+ret)%MOD;
        }
    }
}


signed main(){
    dodp();
    cin>>T;
    while(T--){
        cin>>n>>m;
        cout<<ans[n][m*2]<<'\n';
    }
    return 0;
}

摩天大楼 / Skyscraper

考虑插入法，从小到大插入可以逃掉绝对值的课。

我们把贡献拆开，考虑每一个$B_i$ 的贡献，发现会有三种可能：$-2B_{i},0,2B_{i}$。而具体选哪个取决于左右两侧的数是否比他大。

我们按照值域的顺序来插入，从小到大插，这个时候我们要确定的是绝对位置。$f(i,j,k)$ 表示当前到第$i$ 个值，形成$j$ 个连续段，当前所有数贡献为$k$ 的方案数。

转移时还是三个讨论情况，但新的数两侧是否紧贴着连续段就代表了两侧的数是否比他大。由于序列的两侧不能再插入元素，因此还需要记录两个 0/1 变量表示当前序列的左右两侧是否已经被占据了。

还是接着讨论三个情况，时间复杂度$O(n^3L)$，但是代码写了 1145 行，于是不放了 www。

3. 枚举最大值转移DP

枚举最大值转移 DP，实际上就是排列在笛卡尔树结构上的 DP（注意不是真正的笛卡尔树），有点类似于分治的思想。其作用就是用来解决一类取最大值和最小值的排列计数题型。接下来均以最大值来举例子：

我们利用的是一个笛卡尔树的性质：我们设一个区间$[l,r]$ 最大值的位置为$pos$，发现可以把区间分成$[l,pos]$ 和$[pos,r]$ 两个区间，并且两个区间互不影响，也就是说我左边怎么乱搞放数也不会影响右边的区间。这个时候全局最大值作为区间的端点出现。

我们可以自底向上类似 “树形 DP” 来合并区间，然而实际上我们在计数 DP 里大多数情况并不能真的建立笛卡尔树跑 DP。通常来说，我们会枚举这个区间最大值（即笛卡尔树的 “根节点”）的位置出现在哪里，我们在这里不妨设位置为$k$，区间长度为$i$，枚举之后，会从左儿子即$k-1$ 和右儿子$i-k$ 转移过来（注意这里舍弃了中间最大值的元素），但我们仍要考虑分配左儿子权值的情况，也就是说我们要乘上$\binom{i-1}{k-1}$ 分配的情况。

其本质就是类似于笛卡尔树的分治结构，我们在合并时确定相对大小，把组合数乘起来，但要注意的是，我们这种方法其实是从小到大逐一确定值的扫描线顺序。

PA2018 Skwarki

首先考虑计数 DP，但是直接做发现不太好做，我们思考能否对删除操作进行进一步转化成好的条件取做。

对于原题目的限制，即只要一个数左右两侧一旦有一个大的就会被删，既有位置限制和数值限制。一步很妙的转化的就是将这个思想转成笛卡尔树，那么删除操作就是在笛卡尔树上删有儿子的点。

我们不妨设$g_{u}$ 表示删空$u$ 子树（包括$u$ 号点）的所需次数，因为题意表明删除操作是同时进行的，不难有如下转移：

$$g_{u}=\max\left\{ g_{\text{ls}},g_{\text{rs}},\min(g_{\text{ls}},g_{\text{rs}})+1 \right\}$$

其中 ls 表示左儿子，rs 表示右儿子，注意在没有左儿子和右儿子的时候要特判。

方程表明如下情况：

• $g_{\text{ls}},g_{\text{rs}}$：因为操作是并行的，我们可以直接对左右儿子删除操作取$\max$ 即可。
• 某一子树删除完毕后，花一次操作删根节点$u$ 让后把剩下子树接上去。

注意到删除最多删除树的一半节点，也就是当删除操作数量$k\le \log(n)$ 时才可能有解。

验证考虑分类讨论，讨论左右子树操作次数相同和不同的情况即可简明验证。不难发现的一点是答案一定是全局的最大值，并且一定作为叶子节点出现。

接下来我们考虑如何把它搬到计数 DP 上，真的在笛卡尔树上 DP 显然是不现实的，因为树的结构会改变，考虑我们上面所提到的，我们可以这么设置方程：设$f(i,j,0/1)$ 表示共$i$ 个元素的排列，恰好$j$ 次删空，全局最大值是否在区间的端点。

对于$f(i,j,0)$ 的转移，根据我们上面所述的笛卡尔树的节点，我们需要枚举区间的最大值的位置来进行转移，对于每个位置$k$ 在分配左儿子的方案有$\binom{i-1}{k-1}$ 种方案给乘起来，左儿子$f(k-1,l,0)$ 右儿子$f(i-k,r,0)$，其中$l,r$ 是枚举儿子区间最大值的位置，转移即可。

考虑$f(i,j,1)$ 的转移，我们不考虑区间端点到底在哪里，因为排列的对称性可以完全统计答案，那么转移只需统计左儿子或者右儿子任一出现最大值的方案数即可，再乘上$\binom{i-1}{k-1}$ 即可。

转移的$j$ 需要通过上面的$g$ 单独计算，答案统计仍枚举最大值转移即可，见代码，时间复杂度$O(n^{2}k^{2})$。

注意到$k$ 最大为$\log(n)$，那么时间复杂度就是$O(n^2 \log^{2} n)$，这个复杂度下会被卡常，需要减少取模操作。注意到转移方程可以前缀和优化，那么时间复杂度即为$O(n^{2} \log n)$，这里就不用关心了。

CF1580B

$O(n^5)$ 很幽默吗？

考虑笛卡尔树排列 DP，问题转化为求笛卡尔树深度为$m$ 的点有$k$ 个排列的个数，考虑 DP，设$f(i,j,k)$ 表示共$i$ 个数，笛卡尔树上深度为$j$ 的节点有$k$ 个，考虑枚举最大值转移，枚举左侧有$q$ 个深度为$j$ 个节点，贡献为$f(p-1,j-1,q)\times f(i-p,j-1,k-q) \times \binom{i-1}{p-1}$，$O(n^5)$ 卡常即可，实在不行因为很多答案为$0$，考虑设$g(i,j)$ 表示共$i$ 个数，深度为$j$ 的节点最多有多少个，简单 DP 即可，时间复杂度$O(n^3)$。

不要开 long long！

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=101;
int f[MN][MN][MN],C[MN][MN];
int g[MN][MN],pw[MN],inv[MN],n,m,K,MOD;

void init(){
    pw[0]=1;
    for(int i=1;i<MN;i++) pw[i]=1ll*pw[i-1]*i%MOD;
    for(int i=0;i<=n;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }
}

int getC(int a,int b){
    if(a<b||a<0||b<0) return 0;
    return C[a][b];
}

signed main(){
    cin>>n>>m>>K>>MOD;
    init();
    g[1][1]=1;
    for(int i=2;i<=n;i++){
        g[i][1]=1;
        for(int j=2;j<=i;j++){
            for(int k=1;k<=i;k++){
                g[i][j]=max(g[i][j],g[k-1][j-1]+g[i-k][j-1]);
            }
        }
    }
    if(K>g[n][m]){
        cout<<0;
        return 0;
    }
    f[1][1][1]=1;
    for(int i=0;i<=n;i++) f[0][i][0]=1;
    for(int i=0;i<=n;i++) f[1][i][0]=1;
    f[1][1][0]=0;
    for(int i=2;i<=n;i++){
        f[i][1][1]=pw[i];
        for(int j=2;j<=min(i,m);j++){
            for(int k=0;k<=min(i-j+1,K);k++){
                for(int p=1;p<=i;p++){
                    for(int l=0;l<=k;l++){
                        (f[i][j][k]+=(long long)f[p-1][j-1][l]*f[i-p][j-1][k-l]%MOD*getC(i-1,p-1)%MOD)%=MOD;
                    }
                }
            }
        }
        for(int j=min(i,m)+1;j<=m;j++) f[i][j][0]=pw[i];
    }
    cout<<f[n][m][K];
    return 0;
}

4. 容斥原理与反演

这里的容斥原理与反演就是泛指题型了，主要思想还是利用扫描线或插入法的思想，但是我们利用上述技巧来统计答案或者优化，这一类题型比较偏向于上述的从左往右逐一确定与从小到大逐一确定排名。

例题 P3349小星星

暴力的想法就是定义$f(i,j,S)$ 表示节点$i$ 编号为$j$，子树内编号集合为$S$，时间复杂度$O(n^3 \times 3^n)$，不能通过。

Trick：可以把一个$1$ 到$n$ 的排列可以看作每个元素至少出现一次或至多出现一次。

考虑扫描线确定值，定义$f(i,j)$ 表示节点$i$ 编号为$j$ 的方案数，注意到有重复元素，套路的进行状压，钦定树上每个点的编号必须是$S$ 的子集，考虑容斥记录答案，即$S(n)-S(n-1)+S(n-2)-\dots$，时间复杂度$O(n^3\times 2^n)$。

或者钦定某些元素不能出现，设为集合$S$，做$O(n^3)$ 的树形 DP，这里还是定义$f(i,j)$ 表示节点$i$ 编号为$j$ 的方案数，但是要求$j \notin S$，设得到的答案为$g(S)$，答案为$\sum\limits (-1)^{|S|} g(S)$，复杂度同上。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=18;
int n,m,f[MN][MN],ans;
vector<int> adj[MN],lst;
bool mp[MN][MN];

void init(){
    memset(f,0,sizeof(f));
    lst.clear();
}

void dfs(int u,int pre){
    for(auto p:lst) f[u][p]=1;
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs(v,u);
    }
    for(auto p:lst){
        for(auto v:adj[u]){
            if(v==pre) continue;
            int sum=0;
            for(auto q:lst){
                if(!mp[p][q]) continue;
                sum+=f[v][q];
            }
            f[u][p]*=sum;
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        mp[u][v]=mp[v][u]=1;
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<(1<<n);i++){
        init();
        for(int j=1;j<=n;j++){
            if(!((i>>(j-1))&1)) lst.push_back(j);
        }
        dfs(1,0);
        int sum=0;
        for(auto p:lst) sum+=f[1][p]; 
        ans+=sum*(((__builtin_popcount(i))&1)?-1:1);
    }
    cout<<ans;
    return 0;
}

练习：LOJ575 不等关系（分治 NTT）

5.总结

到了这里，我们可以基本了解对于排列令项限制问题的基本形式，基本思路以及基本套路。

事实上，对于限制的排列计数问题，其核心思想是围绕着插入法来进行操作的。除插入法的核心操作之外，我们还有一些优化技巧，例如连续段和枚举最大值转移。对于容斥原理是扫猫线上的一类统计答案的技巧，通过一些计数技巧来优化时间复杂度或者统计答案。

可能一些题和类型我还是没见过的，欢迎大家在讨论区分享。

---

参考：

• YeahPotato的dp 题方法总汇

• ListenSnow的CF995F题解

• ChroneZ的浅谈一类处理状态转移依赖邻项的排列计数问题的 dp 策略

• Cultreborn的组合数学知识简明大全

• 蓝书

• 云浅之处的容斥与反演技巧

看在这么用心的文章上，求留个赞再走吧！awa

哦对这是我的博客不是洛谷，好像不能点赞www，那就求贯注主播谢谢喵~。