前言
今天的题目也是比较快速的做完了。
所以先来总结一下。
今天是计数专题，组合数居多。
以前做过的题目这里就稍稍略过了。
Merge Triplets
观察到对于能够得到的最终的排列 \(p\)，对于其中的一个数 \(p_i\)，不可能做到 \(p_i>\max_{j=i+1}^{i+3}p_j\)。
感觉是比较显然的，这里就不仔细证明了。
为了方便转化这个性质，我们考虑对 \(p\) 求一个前缀 \(\max\) 数组 \(q\)，他一定满足最长的连续相同的段 \(\le 3\)。
而我们看每一个块对这个连续段的贡献，一定会分为以下三种：
-
直接贡献一个长度为 \(3\) 的相同段。
-
贡献三个长度为 \(1\) 的相同段。
-
贡献一个长度为 \(1\) 的相同段和一个长度为 \(2\) 的相同段。
我们考虑相同段满足哪些条件才是充分的。
首先一个很必要的是所有相同段的长度 \(\le 3\)，但是显然满足这个条件的排列不一定能被构造出来。
然后我们观察上面的三种贡献可以得到一个点：长度为 \(1\) 的相同段的个数一定 \(\ge\) 长度为 \(2\) 的相同段。
而这两个条件加起来就是充分的了，也就是说只要满足这两个条件的所有排列都是合法的。
但是显然我们不能把长度为 \(1\) 的相同段和长度为 \(2\) 的相同段的个数都记下来，这显然时间复杂度会炸。
故我们考虑记录长度为 \(1\) 的相同段和长度为 \(2\) 的相同段个数的差。
定义 \(dp_{i,j}\) 表示算了 \(i\) 个块的贡献，长度为 \(1\) 的相同段个数 \(-\) 长度为 \(2\) 的相同段个数为 \(j\)。
转移如下：
dp[i + 1][j + 1 + m] += dp[i][j + m], dp[i + 1][j + 1 + m] %= mod;
dp[i + 2][j - 1 + m] += dp[i][j + m] * (i + 1ll) % mod, dp[i + 2][j - 1 + m] %= mod;
dp[i + 3][j + m] += dp[i][j + m] * (i + 1ll) % mod * (i + 2) % mod, dp[i + 3][j + m] %= mod;
看上去有点抽象对吧。确实是这样的。
我们以第三行的转移为例来解释。
你可以考虑把他理解成一个树上拓扑序的个数，即我们定义第 \(i\) 个块的第 \(j\) 的数为 \((i,j)\)。那么你考虑将 \((i,1)\) 与 \((i-1,1),(i,2),(i,3)\) 连边，本质上就是表示他比这三个数大。
而你把他理解为拓扑序的方案数就可以得到上述转移。
/*
纵使我发现了不可能x[1]>x[2],x[3],x[4]
我也想不到前缀MAX会相同
qwq
*/
#include <bits/stdc++.h>
using namespace std;
#define maxn 6005
int m = 6000;
int dp[maxn][maxn << 1];
int n, mod;
int main()
{
cin >> n >> mod;
n *= 3, dp[0][m] = 1;
for (int i = 0; i < n; ++i)
{
for (int j = -i; j <= i; ++j)
{
if(!dp[i][j + m]) continue;
dp[i + 1][j + 1 + m] += dp[i][j + m], dp[i + 1][j + 1 + m] %= mod;
dp[i + 2][j - 1 + m] += dp[i][j + m] * (i + 1ll) % mod, dp[i + 2][j - 1 + m] %= mod;
dp[i + 3][j + m] += dp[i][j + m] * (i + 1ll) % mod * (i + 2) % mod, dp[i + 3][j + m] %= mod;
}
}
int ans = 0;
for (int j = m; j <= 2 * m; ++j) ans += dp[n][j], ans %= mod;
cout << ans << endl;
}