AGC043D Merge Triplets

pufanyi

题解

发布于：Mar 31, 2020

给出一种生成长度为 $3n$ 的排列 $P$ 的方法：

先生成一个长度为 $3n$ 的排列 $A$ ，然后对于 $\forall k\in [0,n-1]$ ，将 $3n + 1, 3n + 2, 3n + 3$ 分成一块。
有 $n$ 个指针，开始指向这 $n$ 个块的开头。
每次选择这 $n$ 个指针指向的数中最小的并将其放在 $P$ 的末尾，将这个指针向后移一位，如果移出块了，将指针删除。
回到 2 操作直到所有指针均被删除。

现在要你求出，这样的方式共能生成多少种本质不同的排列 $A$ ，答案对 $m$ 取模。

$1\le n\le 2\times 10^3,10^8\le m\le 10^9+7$

首先我们不难发现这个序列在一定程度上肯定是有单调性的，因为本身这个生成的方式就是一个单调的过程。

我们发现对于一个块 $\{a,b,c\}$ ，如果 $a>b$ ，那 $b$ 一定是紧跟在 $a$ 后面的。而如果 $a<b$ ，那么我们不难发现这个快可以分裂成两个，也就是 $\{a\},\{b,c\}$ ，因为 $b$ 肯定在 $a$ 之后选。

那么也就是说，我们现在的情况是，有一些长度为 $1,2,3$ 的块，每个块都是的开头都是最大的。这给我们了一个提示，因为这样的东西给了我们一个将构造方法和序列连结起来的桥梁。因为这个东西与序列一一对应，这个只要将首字母排序一下就可以了。那么我们现在就只要考虑把划分后的块和划分前的块一一对应就可以了。

也就是说我们需要找到其充要条件。我们发现，其实长度为 $3$ 的块再多也不要紧，因为本来的块就是长度 $3$ 的，我们考虑划分后的块。不难发现每次划分要么就是去掉一个长度为 $3$ 的块，加上一个长度为 $2$ 的块和一个 $1$ 的块，要么就是将一个 $2$ 的块划分成两个 $1$ 的块。我们考虑这件事情，就不难发现这个条件了： $2$ 的块数小于等于 $1$ 的块数。

现在我们只要将划分完的块拼起来就可以了。也就是说，一个序列合法的充要条件是：存在一种划分方案，使得划分后每个块大小小于等于 $3$ ，而且每个块的开头是块中最大的，且比其之前的数都要大。经过之前的推导，我们也知道了这种划分方案是唯一的。

我们思考这东西怎么计算，我们先考虑如果划分方案已经给出，数字随便填，这样有几种方案。

我们发现，一些限制就是： $a_i$ 在 $[1,r]$ 中是最大的。如果长度为 $n$ ，那么答案就是 $\frac{n!}{\prod r}$ 。于是我们用这个性质就可以 dp 了。

我们令 $f_{i,j}$ 表示如果排列的长度为 $i$ （只能填前 $i$ 个数），长度为 $1$ 的块的个数减去长度为 $2$ 的块的个数为 $j$ 的方案数。其实就是考虑右面加一个什么样的块。根据上面的式子，我们不难得到：

\begin{cases} f_{i+1,j+1}&\leftarrow&f_{i,j}&\text{$i+1$ 被除掉了}\\ f_{i+2,j-1}&\leftarrow&f_{i,j}\cdot(i+1)&\text{$i+2$ 被除掉了}\\ f_{i+3,j}&\leftarrow&f_{i,j}\cdot(i+1)\cdot(i+2)&\text{$i+3$ 被除掉了} \end{cases}

然后就可以愉快地转移啦！

namespace dfcmd {
    typedef long long LL;
    
    const int maxn = 2000;
    const int base = maxn * 3 + 2;
    
    int n, mod;
    int f[maxn * 3 + 5][maxn * 6 + 5];
    
    inline void add(int& x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }
    
    int main() {
        read(n), read(mod);
        n *= 3;
        f[0][base] = 1;
        for (register int i = 0; i < n; ++i) {
            for (register int j = 1; j <= base << 1; ++j) {
                add(f[i + 1][j + 1], f[i][j]);
                add(f[i + 2][j - 1], (LL) f[i][j] * (i + 1) % mod);
                add(f[i + 3][j], (LL) f[i][j] * (i + 1) * (i + 2) % mod);
            }
        }
        int ans = 0;
        for (int i = base; i <= base << 1; ++i) {
            add(ans, f[n][i]);
        }
        writeln(ans);
        return 0;
    }
}