AGC043D Merge Triplets

比这个 C 简单太多了。

我们考虑最终的排列中的一个位置 $P_i$ ，如果有 $P_i < P_{i-1}$ ，那么一定是拿完 $P_{i-1}$ 后立即拿 $P_i$ ，且 $P_{i}$ 一定出现在 $P_{i-1}$ 的序列中的下方。

我们考虑这个序列的前缀最大值序列，很显然两个前缀最大值中间不能间隔超过 $2$ ，因为中间间隔的数必须是选择了上一个数后立即在它对应序列下方选择的。

考虑什么样的序列能够被构造出来。我们假设有 $a_k$ 个前缀最大值后面跟着 $k$ 个比它小的数，那么 $a_2$ 是不会对整个序列造成影响的，因为这样的三个数可以自己形成一个长为三的序列。同时，$a_0 \ge a_1$ 必须被满足，因为对于每一个 $a_1$ ，相当于存在一个序列中它的两个位置都被确定了，还剩下一个位置，可以发现只能使用 $a_0$ 中的数填入。最后，$a_0-a_1$ 必须是三的倍数，因为剩下的 $a_0$ 只能三个三个自己组成序列。

假设我们确定了前缀最大值的位置以及它后面跟着多少个比它小的数，怎么确定此时的方案数呢？我们可以把统计排列的过程看成一个一个插入数的过程，那么如果跟着一个前缀最大值，那么方案只有 $1$ ，如果跟着的是非前缀最大值，那么方案就是当前选择的数的个数。所以我们可以在前缀最大值的位置除掉一个系数，最后给答案乘上 $(3n)!$ 即可。

因此做法就很显然了：设 $dp[i][j]$ 表示当前填入了 $i$ 个数，$a_0-a_1$ 的大小是 $j$ ，转移：

$$dp[i][j] \to dp[i + 3][j] \times \frac{1}{i + 3}\\ dp[i][j] \to dp[i + 2][j + 1] \times \frac{1}{i+2}\\ dp[i][j] \to dp[i - 1][j - 1] \times \frac{1}{i + 1}$$

最后给所有 $dp[n][-3k]$ 的位置加起来并且乘上 $(3n)!$ 即可。

复杂度 $O(n^2)$ 。

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 6e3 + 10;
int P;
int n;
int f[MAXN][MAXN * 2] , J[MAXN] , iJ[MAXN] , iv[MAXN];

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

void Inc( int& a , int b ) {
    a = ( a + b < P ? a + b : a + b - P );
}

void solve() {
    cin >> n >> P;
    J[0] = 1;
    rep( i , 1 , n * 3 ) J[i] = J[i - 1] * 1ll * i % P , iv[i] = Pow( i , P - 2 );
    iJ[n * 3] = Pow( J[n * 3] , P - 2 );
    per( i , n * 3 , 1 ) iJ[i - 1] = iJ[i] * 1ll * i % P;
    const int B = 3 * n + 1;
    f[0][B] = 1;
    rep( i , 0 , n * 3 - 1 ) rep( j , 0 , n * 4 + 2 ) if( f[i][j] ) {
        Inc( f[i + 2][j + 1] , f[i][j] * 1ll * iv[i + 2] % P );
        Inc( f[i + 3][j] , f[i][j] * 1ll * iv[i + 3] % P );
        if( j ) Inc( f[i + 1][j - 1] , f[i][j] * 1ll * iv[i + 1] % P );
    }
    int ans = 0;
    for( int t = 0 ; t <= n * 3 ; t += 3 )
        Inc( ans , f[n * 3][B - t] );
    cout << ans * 1ll * J[n * 3] % P << endl;
}

signed main() {
	//  freopen("in","r",stdin);
	// freopen("out","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}