首先，假设我们已经知道了$A_1,A_2,\ldots,A_n$，然后考虑一下最后的$P$大概会长什么样子。

比如现在假设有一个序列$x={x_1,x_2,x_3 }$，如果$x_i>x_{i+1}$，那么在选择了$x_i$之后一定会选择$x_{i+1}$。因此按从前往后的顺序看$x$，如果$x_i$比之前的所有$x_i$都要大，就在其前面放置一个“中断”，然后一次选择“中断”间（这里认为两端也算“中断”）的一整个块。

选择一个块的时间由该块的第一个值决定，且该块开头的值按照一个顺序从前面开始单调递增。因此，$P$是按照第一个值排序的块序列。

那么反过来说，这些块是从$P$唯一确定的。

考虑如何将它们分配给$A_1,A_2,\ldots,A_N$

可以证明，一个合法的$P$一定可以按照以下几个条件构造出来：

将$P$划分为块，且这些块的大小满足

  • 每个块的大小不超过3个。
  • 大小为2的块数量$\leq$大小为1的块的数量。

那么假设一开始块的大小分别为$a_1,a_2,\ldots ,a_K$。而满足条件的排列的数量即 $$ \frac{n!}{a_1\cdot(a_1+a_2)\cdot \ldots \cdot (a_1+a_2+\ldots +a_K)} $$ 然后考虑$dp$求出答案。

令$dp_{i,j}$表示所有$\frac{N!}{a_1\cdot (a_1+a_2)\cdot \ldots \cdot (a_1+a_2+\ldots +a_K)}$对于所有的$a$，其中$i=\sum a,j=$长度为$1$的段的数量$-$长度为$2$的段的数量。具体转移为 $$ dp_{i,j}+=dp_{i-1,j} $$

$$ dp_{i,j}+=dp_{i-2,j-1}\cdot (i-1) (i\ge 2,j\ge 1)
$$

$$ dp_{i,j} +=dp_{i-3,j-1}\cdot(i-1) \cdot (i-2)(i\ge 3,j\ge 1) $$

（系数是从上面那个式子中除下来的）

时间复杂度$O(n^2)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

inline void add(int &x,const int &y){x+=y;x>=m?x-=m:1;} 
signed main()
{
	n=read(),m=read();
	dp[0][0]=1;
	R(i,1,3*n) R(j,0,n)
	{
		add(dp[i][j],dp[i-1][j]);
		if(i>=2&&j) add(dp[i][j],dp[i-2][j-1]*(i-1)%m);
		if(i>=3&&j) add(dp[i][j],dp[i-3][j-1]*(i-1)%m*(i-2)%m);
	}
	int ans=0;
	R(i,0,n) add(ans,dp[3*n][i]);
	writeln(ans);
}