排列相关计数 笔记

本文复制自以往相关笔记，添加了部分内容。

类型一

在此类 DP 中，我们按下标顺序往答案插入，即从前往后逐一确定在当前前缀中的排名等信息，详见例题。

1. AT_dp_t Permutation / UVA1650 数字串 Number String

实际上，对于 $1\sim 6$ 的一个排列，如果 1 2 6 5 4 3 是合法的，那么 1 3 8 6 7 5 也是合法的。

也就是说，题目并不关心这几个数是否真的是 $1\sim 6$ 的一个排列，所以可以考虑不考虑这些数值的实际大小，而是关心他们相对的排名。

设 $f_{i,j}$ 表示处理好前 $i$ 个位置，其中第 $i$ 个位置放在这 $i$ 个数中排名为 $j$ 的数。

如果这一位需要比前一位大（这一位是 $<$），那么：

$$f_{i,j}=\sum _{k=1}^{j-1}{f}_{i-1,k}$$

如果这一位需要比前一位小（这一位是 $>$），那么：

$$f_{i,j}=\sum _{k=j}^{i-1}{f}_{i-1,k}$$

2. P7986 [USACO21DEC] HILO P

发现当前这个数能不能报出 HI 或者 LO 和他在前缀中的排名有关，于是考虑按下标插入。

设 $f_{i,j,0/1}$ 表示考虑前 $i+j$ 个数，其中 $\le x$ 的有 $i$ 个，$>x$ 的有 $j$ 个，当前最后报的是 LO/HI 的方案数，设 $g_{i,j,0/1}$ 的状态与 $f$ 一致，但是表示的是 HILO 的个数总和，即答案。

这也是种常见的辅助数组状态设计，当可以计入答案时，再将 $f\to g$，于是考虑 $(i-1,\ast ,\ast )\to (i,\ast ,\ast )$ 转移，转移有六种情况，其中有五种没有产生新的 HILO，$f$ 与 $g$ 的转移一致。

1. 当前插入数 $\le x$，HI 转移至 LO，此时要求插入的数在 $\le x$ 中排名最大，并且此时 $f$ 对 $g$ 有贡献，因此：

$$f_{i-1,j,1}\to f_{i,j,0}$$$$g_{i-1,j,1}+f_{i-1,j,1}\to g_{i,j,0}$$

2. 当前插入数 $\le x$，LO 转移至 LO，此时不需要考虑当前数是否增加了新 LO，排名任意：

$$f_{i-1,j,0}\times i\to f_{i,j,0}$$

3. 当前插入数 $>x$，LO 转移至 LO，说明当前插入数想加入 HI，但是失败了，即排名并非最小：

$$f_{i,j-1,0}\times (j-1)\to f_{i,j,0}$$

剩下三种转移至 HI 也是一样的，但是 LO 转移至 HI 对 $g$ 无额外贡献。

状态数 $O(n^2)$，转移 $O(1)$，时间复杂度 $O(n^2)$，空间复杂度用滚动数组优化到 $O(n)$。

类型二

此类型中，我们按值以一定的顺序（如从小到大）加入到答案中，此时又有两种情况：

1. 考虑插入的位置进行转移。

2. 记录某些关键点的信息，预定最终排列这些关键点上的值记为状态。

1. CF1806D DSU Master

面对稀奇古怪的题面，要尝试进行数学转换使其形式化。

在本题中，考虑最终排列 $p$，当 $p_i$ 满足 $a_{p_i}=1$ 且 ${\mathrm{mex}}_{j<i}(p_j)=p_i$ 时，若 $a_i=1$，则 $\ge p_i$ 的数如何插入对答案无贡献；否则，当前还有贡献的排列新增了贡献。可以看出这和值的大小有关，于是考虑从小到大插入排列。

设 $f_i$ 表示考虑 $[1,i]$ 组成的排列，贡献截止到 $\le i$ 的总答案，$g_i$ 表示 $[1,i]$ 组成的排列中，还能造成贡献的有多少个。

当 $a_i=0$ 时，任意放对答案有贡献，故 $f_i\leftarrow f_{i-1}\times i+g_{i-1}$，$g_i\leftarrow g_{i-1}\times i$。

当 $a_i=1$ 时，放最后对答案无贡献，故 $f_i\leftarrow f_{i-1}\times i$，$g_i\leftarrow g_{i-1}\times (i-1)$。

答案即为 $f_n$，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

2. P5999 [CEOI2016] kangaroo

这是一个经典的按段数的插入 DP，特点是可以看作当前状态是答案从左往右，依次组成若干段合法的答案，相同段数的多种情况没有区别，而每次插入数，都是往某一段的两端插入，DP 记录了段数为状态。

设 $f_{i,j}$ 表示前 $i$ 个数组成了 $j$ 段答案的方案数，答案即为 $f_{n,1}$。

状态是什么意思呢？比如对于上面 T1，现在求出三部分答案区间：$(1)$，$(5,3)$，$(2,4)$，这些区间内部都必须满足答案要求的性质。这就是 $f_{5,3}$ 包含的一种方案。

对于这样的状态，一般有三种操作：

1. 随便挑一段区间将第 $i$ 个数接到它的结尾：

$$f_{i,j}=f_{i-1,j}\times j$$

2. 自己开一段区间，由于这一段区间可能插在上一个状态的 $j-1$ 段形成的 $j$ 个空（包含序列两端也可以插入）中的任意一个空中，所以：

$$f_{i,j}=f_{i-1,j-1}\times j$$

3. 合并左区间和右区间，自己放到中间，上一个状态的 $j+1$ 段只有 $j$ 个“中间”（序列两端的，显然不能合并），所以：

$$f_{i,j}=f_{i-1,j+1}\times j$$

回到这一题。这道题的本质是求上面 T1 中的 $><\cdots ><$ 序列和 $<>\cdots <>$ 序列的总方案数，只不过固定了开头数和结尾数。

用同样的方法设状态，从小到大考虑插入每一个数。

• 不存在第一种操作，因为从小到大考虑，要是个个数都直接往前面序列的后面接，必然会形成一个完全单调递增的“答案序列”，和题意不符。

• 第二种操作必然合法，它新开一段区间，前后都没有数，没有大于小于的比较。

• 第三种操作必然合法，因为从小到大考虑，现在考虑的数肯定比之前的数都要大，把自己放到中间合并任意两个区间，都能构成以自己为中心的 $<>$。

3. CF1437F Emotional Fishermen

考虑从大到小将 $x$ 插入序列，那么就只需要考虑 $2x\le y$ 的限制。

考虑记录排列第一个位置的值 $p_1$，若当前插入的 $x$ 使得 $2x\le p_1$，那么就可以从开头插入，否则 $2x\le 2p_1\le p_i(i>1)$，他可以插入除了 $p_1$ 周围两个空以外的任意位置。

于是 DP 即可。

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