[AGC043D] Merge Triplets

Genius_Star · 2026-09-04 19:53:26 · 题解

或许更好的阅读体验。

思路：

考虑找到最终什么样子的排列是合法的，可以被生成的，找一下性质。

一个比较显然的性质是：

对于每个数组的第一个元素，加入 p 时一定是作为前缀最大值出现的。

证明比较简单，因为它一直是 n 个开头元素中的一个，所以前面选的都是比它小的，则它必然是一个前缀最大值。

然后继续找性质，如果 a_{i, 1} 被选了：

且 a_{i, 2}, a_{i, 3} < a_{i, 1} 即 a_{i, 1} 是三个中的最大值，那么接下来一定会把 a_{i, 2}, a_{i, 3} 一起选了（因为 a_{i, 1} 已经是开头中最小的了，把它删了加入更小的，那最小的肯定是那个更小的）。
否则其它情况，要么 a_{i, 2} 跟着 a_{i, 1} 一起选，要么 a_{i, 3} 跟着 a_{i, 2} 一起选，或者 a_{i, 1} < a_{i, 2} < a_{i, 3} 不会出现跟随的情况。

那这个跟随本质是什么，第一个本质上是在前缀最大值 a_{i, 1} 后面跟了一个或者两个非前缀最大值，那 a_{i, 2} 插入进 p 的时候呢？因为它没有跟随 a_{i, 1} 走，所以 a_{i, 2} > a_{i, 1} 且它也在 a_{i, 1} 走后一直是开头候选之一，前面选的都是比它小的，所以 a_{i, 2} 也是前缀最大值，于是如果 a_{i, 3} 跟着 a_{i, 2} 走的，本质上是一个前缀最大值后面跟了一个非前缀最大值的情况。

所以回到最终序列 p，每次它前缀最大值出现时，后面最多跟两个非前缀最大值，相当于对于非前缀最大值构成的连续段长度不超过 2 且数量不超过 n。

你发现这个条件是充要的，通过这个你一定可以构造出一组 a 来，具体的：

前缀最大值后面跟两个的情况，直接三个放一块。
跟一个的情况，如果前面还有单独的前缀最大值，则随便拿个拼起来放一起就行，否则找一个后面的单独前缀最大值拼一起。
最后剩下的单独的，三个依次拼起来就行。

考虑怎么对这个计数？定义 f_{i, j} 表示只考虑了前 i 个数的相对顺序时，非前缀最大值连续段数量为 j 的方案数，有转移：

直接放一个前缀最大值：

f_{i, j} \gets f_{i - 1, j}

放一个前缀最大值跟一个非前缀最大值：

f_{i, j} \gets f_{i - 2, j - 1} (i - 1)

放一个前缀最大值跟两个非前缀最大值：

f_{i, j} \gets f_{i - 3, j - 1} (i - 2) (i - 1)

直接转移就是 O(n^2) 的，可以通过。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 6060;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, mod;
int f[N][N];
int main(){
    n = read(), mod = read();
    m = (n * 3);
    f[0][0] = f[1][0] = f[2][0] = f[2][1] = 1;
    for(int i = 3; i <= m; ++i){
        f[i][0] = 1;
        for(int j = 1; j <= min(n, i >> 1); ++j){
            f[i][j] = (f[i - 1][j] + 1ll * (i - 1) * f[i - 2][j - 1] % mod) % mod;
            f[i][j] = (f[i][j] + 1ll * (i - 1) * (i - 2) % mod * f[i - 3][j - 1] % mod) % mod; 
        }
    }
    int ans = 0;
    for(int j = 0; j <= n; ++j)
      ans = (ans + f[m][j]) % mod;
    write(ans);
    return 0;
}