题解 AT5801 【[AGC043D] Merge Triplets】

题意：给定如下构造长度为3n的排列P的方法：

• 生成长度为3n的排列A， 然后将 \forall k \in [0, N-1]，A_{3k+1},A_{3k+2},A_{3k+3}分成一块
• 有n个指针，初始指向每个块的第一个数
• 每次选择指针中最小的数放到 P的末尾 ，然后指针指向块内后一个数

求排列P总共有多少种

题解

先手模几个排列P，然后发现这些排列有一些性质

• 排列中存在一些单调的片段，比如

• 每个单调片段的首项递增

构造排列P的方式是有单调性的，所以显然排列P也是有单调性的

若存在A_1>A_2或者A_2>A_3，则这两个数会被相邻地取出

若存在A_1>A_2并且A_1>A_3，则这三个数也会被相邻取出

必然相邻取出的情况分进一个单调内，块的大小不超过3

$\therefore$ 大小为2的块的数量 $\leqslant$ 大小为1的块的数量 在构造块的过程中，一定会按照*块的第一个元素*的大小进行排序构造出一个排列 因此，如果块合法，可以**唯一确定一个排列P**

考虑若块已知，如何填数，方案为\displaystyle\frac{n!}{\displaystyle\prod_{i=1}^{k}(\sum_{j=1}^{i}a_j)}

考虑差值DP

设\texttt {c[i]}表示大小为\texttt i的块的数量

设\texttt {dp[i][j]}表示长度为\texttt i，\texttt {c[1] - c[2]}为\texttt j的排列P的方案数

考虑右边增加的块进行转移

1. 增加大小为1的块

2. 增加大小为2的块

3. 增加大小为3的块

最后答案就是\displaystyle\sum_{\texttt {i=1}}^{\texttt n}\texttt {dp[3 * n][i]}