xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 AT5801 【[AGC043D] Merge Triplets】

考虑已知每个序列,我们是如何构造排列的。

按照题意,每次选择最小的开头放入排列,然后扔掉。

这意味着,由于序列长度为 $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)$。

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

2020-03-23 01:09:37 in 题解