浅谈排列DP计数

wjyppm1403 · 2025-06-12 17:01:23 · 算法·理论

前言

• 2025.6.11 UPD：更新了枚举最大值转移 DP，删除了杂项，大幅重写文章。
• 2025.11.11 UPD：由于 CSPS 考试，文章重构，加入更多的例题，新添加了多个方法。使用了较为严谨化的术语。
• 2025.11.19 UPD：CF1437F 题解错误，感谢 @LightSpot 的指出，修改了例题题解呈现样式，添加了一些提示。
• 2025.11.25 UPD：CF1515F 转移式子错误，感谢 @Lindone 的指出；添加了一道交换求和号的例题，添加了一堆提示；在插入法根据 @tallnut 的建议添加了 P14568 题目，感谢推荐。
• 2025.11.28 UPD：at_dp_t 转移错误，CEOI 2016 kangaroo 修复。

这里没有贡献延后确定，但是有 CSPS 2025 T4 的非延后确定解法。

对于排列计数 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

:::info[提示 1] 这个题给定的是相邻项的限制，直接做容斥不太好做，我们不妨考虑上面的 DP 思想，使用什么方法？ :::

:::success[提示 1 解法] 这个题给定的是相邻项的限制，而且完全没有限定具体取值，直接做容斥不太好做，我们不妨考虑上面的思想，我们考虑插入法。请继续尝试设计 DP 状态！

:::

:::info[提示 2] 观察限制是对大小的限制而非具体值的限制。具体用插入法中的什么方法？尝试设计 DP 状态！

不要害怕算重算漏，分析算重算漏是为什么？ :::

:::success[题解]

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

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

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

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

转移是显然的，我们考虑从 f(i,<j) 和 f(i,\ge j) 转移过来，\ge j 转移中的等于 j 是因为我们在原序列对应第 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

:::success[题解]

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

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

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

:::

P14568 【MX-S12-T3】排列

:::info[提示 1] 只有偏序限制，没有相邻项，考虑什么？ :::

:::success[提示 1 解法] 以相对大小的角度来设计状态。 :::

:::info[提示 2] 如果理解插入法，容易发现它确定的是一个前缀的信息，但是本题目中含有后缀限制。这说明在状态设计中我们不能直接钦定当前元素。

那么我们应该借助什么结构刻画计数对象呢？ :::

:::info[提示 2.1] 尝试思考一种关联：数匹配位置。

每次操作似乎只能在带限制的位置进行填写。 :::

:::success[正解] 我偷懒了大家可以去看 无名之雾的题解 QwQ。

但是我 VP 的时候只会 70 分时何意味，写文章的反而不会排列计数了 QAQ。 :::

切换计数对象

头发不要追我啊啊啊啊。

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

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

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

本质是切换了排列的计数对象。这种方法不仅可以在排列计数中使用，也可以在其他计数题中使用，这种方法方便你可以随时想到如何切换计数对象。

但是问题的关键就是如何提取出那个关键信息 S 以决定计算方式，接下来我们以 2 道例题来看。

例题：AT_agc054_b [AGC054B]

:::info[提示 1] 什么时候无解？ :::

:::success[提示 1 解法] 首先两个人拿到的橘子重量显然为 \dfrac{sum}{2}，显然奇数无解。 :::

:::info[提示 2] 直接尝试进行预定法插入法 DP 求解不太好处理中间的过程限制，似乎我们只会阶乘级别的枚举判断，怎么办？ :::

:::success[提示 2 解法] 考虑交换求和号，有：

请读者先考虑 S 的思考，再考虑 p 的计数。 :::

:::info[提示 3（关于 S 的思考）] 交换求和号的一个目的就是将阶乘级别的暴力枚举转化为更低复杂度级别的暴力枚举。那么什么级别的暴力枚举是我们可以接受的？ :::

:::success[提示 3 解法] 我们发现 2^k 级别的暴力枚举我们是可以接受的，S 可以钦定为一个人选取数的集合，那么我们现在考虑排列的数量如何计算。 :::

:::info[提示 4（关于 p 的思考）] 现在两个人手上分别有集合 S 和 S'。那么排列的计数可以看作两个人每次选出自己集合中的一个数放到排列里面。通过这种角度思考排列的计数方法。 :::

:::success[正解] 交换求和号，有：

其中 S 需要我们进行思考，我们发现 S 可以钦定为一个人选取数的集合。

那么这个选取集合的方案数是及其容易求出的，但是排列的数量需要我们思考一下，我们发现对于固定的 S，其对应的排列是 |S|!\times (n-|S|)!。原因是将两个人手中的数一个一个放进去总存在方法一一对应放进去，如果不能放显然矛盾。

那么就好说了，那么考虑 DP，设 f(i,j,k) 表示前 i 个数，已经选择了 j 个，总和为 k。那么答案计算就是 \sum\limits_{i=0}^n f(n,i,\dfrac{sum}{2})\times i!\times (n-i)!。时间复杂度 O(n^3)。

将排列计数转化成选数方案计数是这道题的主要难点，首先不好想到，其次想到了证明也不是特别容易。—— M1rai :::

P14364 CSPS2025 员工招聘

:::info[提示 1] 直接进行插入法预定法不太好进行处理过程限制。请思考 10! 的全排列分数，并尝试发掘性质。 :::

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

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

:::

:::info[提示 2] 对于单个信息状态 S，我们需要计算对应排列数。但是容易发现 S 的合法性我们是不太好进行处理的。先尝试思考 S 的合法条件。然后进行排列的计数。 :::

:::success[提示 2 解法] 我们先考虑钦定后所带来的约束，那么对于每一天都有 c 的限制，具体的考虑第 i 天的限制：

• - 若要录取，满足 $c>x_{i}$。 - 若不录取，要求 $c\le x_{i}$。

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

尝试设计 DP 来将集合的枚举和排列的计算融入。 :::

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

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

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

• - 若要录取，满足 $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

:::info 多过程的题目，尝试分析末状态具有什么性质，即最后的序列形如什么？尝试利用这种特殊形式进行 DP。 :::

:::success[题解] 题解来自：quasar

考虑最后的序列一定是：

的形式（其中 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 个数就是在后面的空位里面乱放了：

:::

CF1806D DSU Master

:::success[题解]

一个较为简单的做法，发现如果 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 的方案数，有：

统计一下即可。

:::

枚举最大值转移

枚举最大值转移 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)，转移：

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

PA2018 Skwarki

:::info[提示 1] 原题目的限制，即只要一个数左右两侧一旦有一个大的就会被删，既有位置限制和数值限制。可以怎么转化？如何表示这种删除操作？如何求解？ :::

:::success[提示 1 解法] 将这个思想转成笛卡尔树，那么删除操作就是在笛卡尔树上删有儿子的点。

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

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

方程表明如下情况：

• 某一子树删除完毕后，花一次操作删根节点 u 让后把剩下子树接上去。

:::

:::info[提示 2] 什么时候无解？ :::

:::success[提示 2 解法]

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

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

:::info[提示 3] 考虑如何把它搬到计数 DP 上，注意真的在笛卡尔树上 DP 显然是不现实的，因为树的结构会改变。 :::

:::success[题解]

接下来我们，考虑我们上面所提到的，我们可以这么设置方程：设 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

:::info[提示] 注意数据范围。 :::

:::success[题解]