题解 AT5801 【[AGC043D] Merge Triplets】
xht
2020-03-23 01:09:37
考虑已知每个序列，我们是如何构造排列的。
按照题意，每次选择最小的开头放入排列，然后扔掉。
这意味着，由于序列长度为 $3$，排列中一定不会出现连续四个（或以上）的数 $x_{1\dots 4}$，满足 $x_1 > x_{2\dots 4}$。
因此，**最终的排列中，按照前缀 $\max$ 的位置划分，每一段的长度不超过 $3$**，这是必要条件。
充分吗？不充分，比如 $2\ 1\ 4\ 3\ 6\ 5$ 就不可以。
我们发现，按照前缀 $\max$ 的位置划分，有三个长度为 $2$ 的段，而我们没办法讲其拼成两个长度为 $3$ 的序列。
于是另一个必要条件为，**长度为 $2$ 的段个数不超过长度为 $1$ 的段个数**。
充分吗？充分，因为一旦满足这个条件，我们就能构造出来序列。
那么考虑如何计数，设 $f_{i,j}$ 表示考虑前 $i$ 个数，**长度为 $1$ 的段个数减去长度为 $2$ 的段个数**为 $j$ 的方案数。
转移时枚举下一段的长度 $1/2/3$ 即可，如果长度不为 $1$ 还要额外乘上系数，具体见代码。
时间复杂度 $\mathcal O(n^2)$。
```cpp
const int N = 2e3 + 7, M = N * 3;
int n;
modint f[M][M<<1], ans;
int main() {
rd(n), rd(P), n *= 3;
f[0][M] = 1;
for (int i = 0; i < n; i++)
for (int j = -i; j <= i; j++) {
f[i+1][j+1+M] += f[i][j+M];
f[i+2][j-1+M] += f[i][j+M] * (i + 1);
f[i+3][j+M] += f[i][j+M] * (i + 1) * (i + 2);
}
for (int j = 0; j <= n; j++) ans += f[n][j+M];
print(ans);
return 0;
}
```