发表自己的拙见以及总结一些地方的描述。
需要清晰且合理的认知排列的一些性质，这里设其长度为 \(n\)，值域为 \([1, n]\)：
- 所有元素都不同且出现过恰好一次。
- 所有位置的大小关系始终唯一。
- 建立出的笛卡尔树有严格大小关系。
- 由 \(i \to p_i\) 连边形成若干个度数为 \(2\) 的置换环。
- 交换一个排列的前两个元素，其置换环个数奇偶性发生改变。
- 以及一些其它很优美没被总结进来的性质。
基本理解
对于排列计数，通常是满足一个判定条件 \(\sigma_1(p)\)，其中 \(\sigma_1\) 可以指代一个快速判定 \(p\) 是否合法的函数，通常这种判定条件都能够在 \(O(1) \sim O(n)\) 的时间复杂度内解决，到 \(O(n^2)\) 及以上的部分首先要想想怎么优化判定过程再进行计数。这里需要保证你的 \(\sigma_1\) 足够简单，复杂度足够低，这对于我们的计数部分无疑有巨大的好处。
还有一种类型是过程条件 \(\sigma_1 (\sigma_2(x))\)，其中 \(\sigma_2\) 表示将排列 \(p\) 通过某一维度上按顺序进行某种操作后得到的特征值 \(\alpha\)，而 \(\sigma_1\) 则检验特征值是否满足条件。通常我们希望将 \(\sigma_2\) 构造双射，不去求解 \(\sigma_2\)，探寻特征值 \(\alpha\) 与 \(p\) 的对应关系的充要条件，对 \(\alpha\) 进行计数，通常到了这一步已经不是排列计数了。
生成顺序
一般计数类问题分为两类生成顺序（这无关 DP 的方式，你也可以不用 DP）：
- 按照下标生成。
- 按照值域生成。
两者的区别就是做了一个转置原理。
这里不妨先考虑一些 DP 的方法。
预定 VS 插入
预定就是我们在 DP 的过程中仅考虑当前决策，确定了当前决策的具体量。
插入就是我们在 DP 的过程中考虑当前决策与之前决策的配合，确定了当前决策的相对量。
带排名插入
题目是经典的 AT_dp_t Permutation，这是判定条件类排列计数。
考虑设 \(f_{i, j}\) 表示考虑决策到前 \(i\) 个数的排名第 \(i\) 个数在前 \(i\) 个数中排第 \(j\) 名的方案数。那么转移就枚举当前数的排名是多少，将大于它的排名全部 \(+ 1\)，当然这个过程是隐式的，不会在转移过程中显现出来，使用前后缀和优化即可。
切换计数对象
题目也是经典的 AT_agc054_b [AGC054B] Greedy Division，这是过程条件类排列计数。
那么考虑 \(\sigma_2\) 在干什么，就是在做这个东西的过程，那么特征值 \(\alpha\) 可以表示为 \(\{a, b\}\)，其中 \(a, b\) 分别指第一个人和第二个人按顺序选的数的序列，那么公式化做题，考虑 \(\alpha\) 和 \(p\) 的对应关系的充要条件，仔细想想就知道必定是一一对应，且对于每个合法的 \(\alpha\) 都必定对应一个合法的 \(p\)，可以通过构造说明这件事情。
那么剩下的工作就是一个要统计个数的背包了，这是简单的。
包括像 P14364 [CSP-S 2025] 员工招聘 这种题，同样也是过程条件类，但是由于其 \(\sigma_2\) 的限制特别弱（弱到只是一个前缀判定，且不和上述题目的大小关系搭钩，从实际意义上来看限制实际上比上个题目简单），可以认为 \(\sigma_1\) 将 \(\sigma_2\) 合并了变成一个判定条件类 DP，使用贡献延后计算的 trick 则是为了让这个前缀过程的限制得到充分利用，从这个角度思考问题就变简单了很多。
主次依附转移
题目是 CF1437F Emotional Fishermen。
枚举最大值转移
通常就是 DP 笛卡尔树的形态，比如 AT_arc183_c [ARC183C] Not Argmax。区间 DP 枚举区间最大值进行转移，那么剩下的值通常是无关紧要的（只考虑大小关系，也就是类似排名插入类 DP，每次区间仅关心每个数在其中的大小排名，这样具体大小的限制会根据你 DP 转移的过程一层一层递推下去），预处理哪些部分是不能够成为最大值的部分是好求的。
连续段 DP
这个东西更多基于一种技巧性的直观感受，是插入类 DP 的非前缀版本，将插入的限制利用到位。
之前有个很好的先按值排序再进行连续段 DP 的题我忘记是啥了，就介绍一个简单的版本。
题目是 CF1515E Phoenix and Computers。
设 \(f_{i, j}\) 表示插入了 \(i\) 次，形成了 \(j\) 个段，且 \(j\) 段之间都相隔一个不确定位置的方案数，转移是简单的，具体来说考虑：
- 新增一个数，两个段的合并。
- 新增一个数，一个段的扩张。
- 新增一个数，新建一个段。
可以做到 \(O(n^2)\)，通常只有在这个复杂度下才能使用连续段 DP，不过也有例外就是了（是我记得一个时间复杂度分析出来是 \(O(n \sqrt n)\) 的题）。
按照值来 DP
比如说 P7444 「EZEC-7」猜排列，需要注意到满足 \(f(l, r) = i - 1\) 的区间一定都是包含了一个值在 \([0, i -1]\) 的连续段，那么我们按照值来 DP，设 \(f_{i, j, k}\) 表示插入到 \(i - 1\)，目前前 \(i\) 个数构成的最小区间是 \([j, k]\) 的方式，这是很关键的一步，后面的优化都是基于这个状态的基础上的。
谁说排列计数一定是 DP，我看不一定
按照值来“计数”
我们小学就学过，为什么一个长度为 \(n\) 的排列 \(p\) 有 \(n!\) 种选法。
先按照某个顺序决策一个数放哪里，那么放到第 \(i\) 个数的时候只有 \(n - i\) 个位置可以放了，因此方案数乘上 \(n - i\)，这种做法的可行性在于无论第 \(i\) 个数放哪里都不会影响后面的数的方案数决策，只是空位换了一个相对顺序罢了，因此个数为 \(n!\)。
理解这一步非常关键，给出一个模拟赛题，下面是转化过后的题意：
- 给你排列的前缀最小值和后缀最小值，让你求合法排列个数，可能有一些地方不知道前后缀最小值。
显然，条件限制了某个前缀的数必须大于某个数，某个后缀的数必须大于某个数，且限制条件单调，那么对于值来计数，就是每个值可以填入的位置总是一段连续区间，猜测（实际确实是）所有可以填入区间不交，那么利用上述计数方法，先计算区间小的可以填到多少个位置，再将这个区间内随便一个位置填上即可，可以随便用个数据结构维护。
可以仔细理解一下填入区间不交的妙处。