AT5801 [AGC043D] Merge Triplets

思维/\(DP\)

思维固化，\(AT\)题果然撑不住啊。

需要挖掘生成序列的性质。

可以发现，若有一段区间\(x_l \cdots x_r\)满足\(x_l=\max_{l \le i \le r} x_i\)，那么\(x_l \cdots x_r\)必然是在原序列中的一块，可以从\(l+1 \rightarrow r\)的方式推过去，利用反证法证明。

我们可以用上面的方式把任意一个序列切成很多段（相交的区间可以直接合并）。

我们获得了两个必要条件：

\(1.\)每一段的长度必须\(\le 3\)。

\(2.\)长度为\(2\)的段数必须\(\le\)长度为\(1\)的段数。

我们可以构造序列证明其充分性。

首先，根据我们的划分方式，段与段之间单调递增，表现在一段中的每一个元素都小于下一段的段首，这就保证了一段内的元素是连续取完的。

对于长度为\(3\)的段，它已经完整了，我们将长度为\(1\)的和长度为\(2\)的段随意匹配，然后拼合（拼接两段时，把首元素小的放在前面），多余的\(1\)段也随意匹配（同样拼合段内排序一下）。

对于长度为\(3\)的段，它会一次性取完，和原序列一致。对于\((2,1),(1,2),(1,1,1)\)类型的拼合段，会先取走前一部分，等到比它小的都取走之后取后一部分。由于拼接段时，我们将小的放在前面，必然会导致段与段之间单调递增，比如对于\((a,b),(c,d)(a < c < b < d)\)，一定是较小的\(c\)被先取，因此可以保证它放在\(b\)之前（本质是多路归并排序）。段与段之间单调递增的性质可以在分完段的情况下唯一对应一个序列，也就是原序列。

因此以上两个条件为充要条件，\(dp\)计数即可。

需要的性质是对于段\(a_{1 \cdots r}\)，第\(r\)段的段首一定是\(a_{1 \cdots r}\)中所有值的最大值。

由于需要了解的是\(1,2\)段的段数差，可以考虑差值\(dp\)。

设\(dp_{i,j}\)表示长度为\(i\)的序列，\(1,2\)段的段数差为\(j\)的方案数（这里\(dp\)特殊的一点是，\(dp\)的值为相对顺序，并不确定某一位的真实值，因为\(dp\)到\(n\)时相对顺序就是原序列）。

取长度为\(1\)的段：

\[dp_{i,j} \rightarrow dp_{i+1,j+1} \]

由于这一个值一定为最大值，相对顺序直接继承。

取长度为\(2\)的段：

\[(i+1)dp_{i,j} \rightarrow dp_{i+2,j-1} \]

在相对大小排名中，段首被钦定为最大值，不影响相对顺序。第二位可以从排名为\([1,i+1]\)中的任意一位中抽出，总贡献为\((i+1)dp_{i,j}\)。

取长度为\(3\)的段：

\[(i+1)(i+2)dp_{i,j} \rightarrow dp_{i+3,j} \]

同理。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2005
#define ll long long
using namespace std;
int n,p,dp[N*3][N*6];
void Add(int &x,int y)
{
    x=(x+y)%p;
}
void Mul(int &x,int y)
{
    x=(ll)x*y%p;
}
int add(int x,int y)
{
    return (x+y)%p;
}
int mul(int x,int y)
{
    return (ll)x*y%p;
}
int main()
{
    scanf("%d%d",&n,&p);
    n*=3;
    dp[0][n]=1;
    for (int i=0;i<n;++i)
        for (int j=n-(i >> 1);j<=n+i;++j)
        {
            if (!dp[i][j])
                continue;
            Add(dp[i+1][j+1],dp[i][j]);
            Add(dp[i+2][j-1],mul(i+1,dp[i][j]));
            Add(dp[i+3][j],mul(mul(i+1,i+2),dp[i][j]));
        }
    int ans=0;
    for (int i=n;i<=(n << 1);++i)
        Add(ans,dp[n][i]);
    printf("%d\n",ans);
    return 0;
}

AT5801 [AGC043D] Merge Triplets

AT5801 [AGC043D] Merge Triplets

思维/\(DP\)

推荐阅读