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

可能更洛谷的阅读体验

前言

• 2025.6.11 UPD：更新了枚举最大值转移 DP，删除了杂项，大幅重写文章。
• 2025.11.11 UPD：由于 CSPS 考试，文章重构，加入更多的例题，新添加了多个方法。使用了较为严谨化的术语。

---

对于排列计数 DP，我们侧重研究的是在排列未知的情况下如何计数。

大家显然都是会指数级枚举排列来进行操作，但难点并非对于排列的枚举，而是在于找到一种合适的生成顺序。通过这种顺序，满足题目的限制，将已经生成的部分压缩成少量的关键量，从而把原本指数级的状态降到可解的多项式维度。

本文章将尝试整理和总结我在学习排列计数 DP 时的一些思路和方法。坦白地说，我对这一类问题的理解还不算完全透彻，很多细节可能只有在做了大量例题之后才能真正掌握。所以这里的内容更多是一个学习记录和思路整理，而非什么可以写进 Wiki 的内容。

不过，我写这篇文章希望能够提供一个大概的解题方法，让读者可以在遇见一些计数题目中可以有大致的参考做题方向和状态设计。

基本生成顺序

参考 YeahPotato 博客的分类，基本生成顺序分类如下：

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

预定法

预定法的核心思想就是：每一步直接确定某个位置或某个值的具体量。换句话说，预定法每次操作都是把元素放到一个确定的位置上，而不是在已生成前缀中插入或排列。它更关注的是排列中具体值与位置之间的配对关系。

其特点较为明显，首先是由于我们每次直接确定位置或值，已经生成的部分可以用少量的关键量来进行表示；另一个就是确定性，对于排列中我们每一个值都是确定无误的。

但缺点就是由于我们显然是不可能暴力存储每一个值是否填写，不过我们可以通过题目中的限制在 DP 状态中表示题目所需要的限制，需要我们对于题目有进一步的观察。

其使用一般是在题目中的要求限制是针对于针对具体下标或值例如：

• 第$i$ 个下标只能放给定的数。
• 值$x$ 必须在某个位置范围。
• 构造单调序列时，按值大小逐个确定位置。

我们可以根据前面所提到的配对关系将其划分为两个 DP 主体：值域与位置（或下标）。

以位置为 DP 主体，即我们通过按照下标从左往右确定每个位置的值，一个常见状态就是设$f(i)$ 表示前$i$ 个位置已经填好的排列方案数，每次操作枚举下一个位置可以填的值。一般的情况下会多添加维数记录信息来满足题目中的限制。

同理于按照值域，例如按数值从小到大确定每个值的位置，比如设$f(i)$ 表示已经处理完值域上$[1,i]$ 的元素的方案数，每步确定当前当前枚举到的数放到哪个空位。

在具体选择使用哪个为 DP 主体的时候，需要根据题目中的限制，推出充要条件来进行观察哪个更适合作为主体来推出其他条件。

插入法

插入法，是预定法的对立面，其核心思想就是：每一步不直接确定绝对位置或具体值，而是确定当前元素在已生成前缀中的相对位置或排名。我们每一步操作只关注相对顺序，而非绝对顺序或值。

插入法的特点，我们对于每个元素只确定它在前缀中的插入位置或排名，而不是固定的值或位置。

因为我们只确定顺序，已经生成的部分可以用较为少量的前缀信息来进行表示，而不需要记录整个排列。相对于预定法可以很方便的满足限制，而且 DP 状态很容易设计与想到。

但缺点在于我们每次都是只确定相对位置和排名，牺牲了最终方案中单点元素的准确值。

使用插入法的时候，题目一般限制偏向于顺序，偏序与排名而并非对位置的强制限制，例如：

• LIS，最大值序列长度的限制。属于偏序问题。
• 相对约束而具体位置不重要。

同上，我们也可以划分为两个主体：

按位置为 DP 主体，我们从左往右决定当前值在已生成前缀中的排名，例如设$f(i,j)$ 表示已经处理完前$i$ 个元素，当前取值的相对大小为$j$ 的方案数。适合处理相对顺序限制的问题。

按值域为 DP 主体，本质上我们是只关心插入的顺序，我们在下面会单独提到。

常用方法

通过插入法满足限制

这一类题是偏多的。

AT_dp_t

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

我们考虑 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;
}

交换求和号

一般的情况，原始问题往往是这样，给你一个求排列价值或者判定合法函数$f$，那么答案可以看作：

$$ans=\sum\limits_{p\in \text{所有排列}} f(p)$$

即把所有排列拿出来看一遍，对每个排列计算$f(p)$，最后求和。

然而，我们往往能在$f(p)$ 中提取出一些关键信息$S = \phi(p)$，它决定了$f(p)$ 的计算方式。于是可以将排列按照信息状态$S$ 分组：

$$\sum_{p} f(p) = \sum_{S} \sum_{p: \phi(p) = S} f(p)$$

就是对于排列计数的交换求和号操作，本质是切换了排列的计数对象。

我们以 P14364 来举例。

大家都会$10!$ 的全排列分数，我打的也是这档部分分。那么肯定最后我们要转到 DP，那么怎么转移呢？

容易发现$10!$ 的判定可以如下，设$\phi(p)$ 表示按照排列$p$ 进行面试最终录取情况，那么可以写作：

$$ans = \sum_{p \in \text{所有排列}} [\phi(p) \ge m]$$

我们将其抽象为信息状态$S = \phi(p)$（每天录取情况）。于是可以将排列按信息状态分组有：

$$ans = \sum_{S : \sum_i s_i \ge m} \sum_{p : \phi(p) = S} 1$$

对于单个信息状态$S$，我们需要计算对应排列数。我们先考虑钦定后所带来的约束，那么对于每一天都有$c$ 的限制，具体的考虑第$i$ 天的限制：

• $s_{i}=0$，一定不录取，任意放人都可以。
• $s_{i}=1$，分讨是否录取：
  • 若要录取，满足$c>x_{i}$。
  • 若不录取，要求$c\le x_{i}$。

这是一个有上限也有下限的排列计算，钦定若干下限不满足，则变为只有上限的问题。只有上限的问题是简单的，不妨设为$lim$，将$lim$ 从小到大排列，答案即为$\prod_{i=1}^n (lim_{i}-i+1)$。

基于此，我们可以设计 DP。设$f(i,j,k)$ 表示前$i$ 天的$S$ 安排完毕、当天状态$b_i = j$、上限已经考虑到第$k$ 个的方案数。转移时需要考虑容斥原理处理上限与下限约束的交集，这里不再详细展开。

主次依附转移

这一类转移所体现的题目核心特点就是：确定主要元素，剩余元素的位置受这些主要元素约束。为了降低状态维数，DP 只在主要元素上进行，剩余部分用数学手段如组合数合并计算。如果限制方向与 dp 方向相同则用预定法，否则用插入法。

CF1437F Emotional Fishermen

题解来自：quasar

考虑最后的序列一定是：

$$\boxed{b_1} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_1}{2}\end{matrix} \boxed{b_2} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_2}{2}\end{matrix} \boxed{b_3} \begin{matrix}\underbrace{\cdots\cdots\cdots}\\\leq \frac{b_3}{2}\end{matrix}$$

的形式（其中$a_1\leq \frac{a_2}{2}\leq \frac{a_3}{4} \cdots$） 。

将原序列从小到大排序，定义$lim_i$ 为最大的$j$ 满足$a_j\leq \frac{a_i}{2}$ 。

然后令$dp_i$ 表示$a_i\in\{b_1,b_2,\cdots\}$ 时，当前序列已经放入了$lim_i+1$ 个数的方案数。转移的时候考虑$b$ 序列中上一个位置是多少即可。

如果上一个位置是$j$，首先肯定是将$a_i$ 放在当前序列的第一个非零位置，然后剩下的$lim_i-lim_j-1$ 个数就是在后面的空位里面乱放了：

$$dp_i=\sum dp_j\cdot{n-2-lim_i\choose lim_i-lim_j-1}\cdot (lim_i-lim_j-1)!$$

CF1806D DSU Master

一个较为简单的做法，发现如果$i$ 不插到末尾则无影响，否则当且仅当$1\sim i-1$ 操作结束后根仍然为 1 的时候$a_{i}=0$ 有贡献，本质上是将贡献拆开然后统计。

另一个解法就是发现对答案能造成贡献的是所有$p_{i}=\text{mex}_{j<i}\{p_{j}\}$ 的$i$，对它们 dp，其余部分用组合数插入，设$f(i)$ 表示考虑到$[1,i-1]$ 都在$i$ 之前且目前根仍然为$1$ 的方案数，有：

f(i)=[a_{i}=0]\sum\limits_{j<i}(i-2)^\underline{i-j-1}f(j)

统计一下即可。

枚举最大值转移

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

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

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

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

AT_arc183_c [ARC183C]

模板题。

考虑枚举最大值转移 DP，设$f(i,j,k)$ 表示前$i$ 个元素，当前最大值位置在$j$，区间左端点为$k$ 的方案数，转移是$O(n^5)$。但是我们发现我们都枚举最大值的位置来进行转移了，不用记录最大值位置。直接设$f(i,j)$ 表示前$i$ 个元素，当前所管辖的区间左端点为$j$ 的方案数，注意到可以改写为区间 DP 为$f(l,r)$，转移：

$$f(l,r)=\sum\limits_{k\in[l,r],k \text{ is vaild}} f(l,k-1)\times f(k+1,r)\times \binom{r-l}{k-l}$$

可以随便预处理合法的$k$，时间复杂度$O(n^3)$。

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;
}

连续段 DP

连续段 DP 主要用来解决一类依赖临项后与下标产生关联的计数问题，不光是排列计数问题，这类问题通常的特点是，如果只考虑在序列的两端插入，问题将容易解决（或者说有更简便的状态记录方式）。

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

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

转移考虑：

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

连续段 dp 的方式是将其理解为建立笛卡尔树的过程：

1. 新建叶子节点。
2. 成为某个节点的儿子.
3. 合并节点。

连续段 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(n^2m)$，加点至多把$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。

总结与后言

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

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

参考文献

• YeahPotato的dp 题方法总汇
• ListenSnow的CF995F题解
• ChroneZ的浅谈一类处理状态转移依赖邻项的排列计数问题的 dp 策略
• Cultreborn的组合数学知识简明大全
• 蓝书
• 云浅之处的容斥与反演技巧
• 排列 dp - Oxide - 博客园
• 排列有关 DP/计数 - harmis_yz