OI题解 - Merge Triplets (AtCoder)

好久没打AtCoder的比赛了，但……

---

# 题目

（懒得写翻译了）> AtCoder

---

# 解析

注：本篇博客实为AGC043官方题解的翻译（不是机翻 awa），外加我的一些注释写成的

首先，假设我们已经知道了 $A_1,A_2,\cdots,A_N$，则考虑最后我们会得到怎样一个序列 $P$。注意到对于 $A_1$ 到 $A_N$ 中某一个序列 $X=(x_1,x_2,x_3)$，如果有 $x_i>x_{i+1}(i\le2)$，则我们取出 $x_i$ 后一定会马上取出 $x_{i+1}$。

因此，我们从前往后看 $X$，如果 $x_i$ 比 $x_1$ 到 $x_{i-1}$ 的任何一个数大，则在 $x_i$ 之前设置一个“断点”。这些断点把每个 $A_i$ 分成了几个“块”，并且一个块内的元素会连续被取出（块的第一个数比块内的其他数大）。

定义“比较两个块的大小”为“比较两个块的第一个数的大小”。容易看出在一个块内数字是单调递减的，并且分别看每个 $A_i$，它分出的块是单调递增的。

因此，我们把所有块从小到大排序再依次排列就得到了最后的 $P$。

其实通过上面的解释，每一种“分配 $A_i$”的方式都唯一对应一种分块情况，从而唯一对应一个 $P$。现在就要考虑怎样把初始的 $3N$ 个数分配给 $A_1,A_2,\cdots,A_N$。——倒过来想，我们现在知道 $P$，如何判断是否存在能够构造出 $P$ 的 $A_1,A_2,\cdots,A_N$：

在 $P$ 中插入一些断点使它分成若干块，把这些块分配给 $A_1,A_2,\cdots,A_N$ 使得 $|A_i|=3$

等价于：

把 $P$ 分割成若干块，满足下列要求：

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

如果对于某一个序列 $P$，它能够被分割成满足上述条件的若干块，那它一定可以构造出来。

> Hint

• 因为一个大小为 2 的块必须和一个大小为 1 的块搭配才能构成大小为 3 的 $A_i$，所以必须保证大小为 2 的块的数量不超过大小为 1 的块；
• 假设我们已经知道了 $A_i$ 由哪些块组成，那么我们只要把这些块从小到大排列就能构造出 $A_i$；所以只要能够把分出的块分成 $n$ 个组，每个组的总大小为 3，那么就一定可以被构造出来。

假设序列 $P$ 被分成了大小依次为 $a_1,a_2,\dots,a_k$ 的块（注意到块组成的序列是单增的），那么这样的分法对应的 $P$ 的数量即为：

$$S=\frac{(3N)!}{a_1(a_1+a_2)(a_1+a_2+a_3)\cdots(a_1+\cdots+a_k)}$$

> Hint

不考虑任何限制，$P$ 的个数就是全排列 $(3N)!$

考虑从前往后把 $P$ 分割成若干个块。假设当前正在分配第 $i$ 个块，那么：

• 第 i 个块大于前面任何一个块（因为 $P$ 的构造规则是从小到大取块）
• 第 i 个块的第一个数大于第 i 个块的其他数

因此第 i 个块的第一个数大于前 i 个块中的其他数。

因为前 i-1 个块已经确定了，所以第 i 个块的开头位置也固定了。现在我们要求那个位置是前 i 个块中最大的数，前 i 个块中有 $a_1+a_2+\cdots+a_i$ 个数，因此只有 $\frac{1}{a_1+a_2+\cdots+a_i}$ 的 $P$ 是符合条件的。

又因为每个块是独立分配的，就可以把 $\frac{1}{a_1+a_2+\cdots+a_i}$ 全部乘到一起，就得到了 $S$ 的公式。

于是可以作下面这样的 DP：

定义 dp[s][d]，s 表示 $\sum a_i$（当前的），d 表示“大小为 1 的块的数量 - 大小为 2 的块的数量”，则 dp[s][d] 表示满足上述要求的所有 $S$ 之和。

这样的 DP 转移复杂度 $O(1)$，$s\in[0,3N]$，$d\in[-3N,3N]$，那么总的复杂度就是 $O(N^2)$ 的。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N=6002;
#define f(i,j) dp[i][j+N]

int dp[N+3][N*2+3],inv[N+3];
int n,mod;

int QPow(int a,int b){
	int ret=1;
	while(b){
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&mod);
	f(0,0)=1;
	for(int i=1;i<=3*n;i++)
		f(0,0)=1ll*f(0,0)*i%mod;
	for(int i=1;i<=3*n;i++)
		inv[i]=QPow(i,mod-2);
	for(int i=1;i<=3*n;i++)
		for(int j=-3*n;j<=3*n;j++){
			f(i,j)+=f(i-1,j-1);
			if(i>=2) f(i,j)+=f(i-2,j+1);
			if(f(i,j)>=mod) f(i,j)-=mod;
			if(i>=3) f(i,j)+=f(i-3,j);
			if(f(i,j)>=mod) f(i,j)-=mod;
			f(i,j)=1ll*f(i,j)*inv[i]%mod;
		}
	int ans=0;
	for(int j=0;j<=3*n;j++){
		ans+=f(3*n,j);
		if(ans>=mod) ans-=mod;
	}
	printf("%d\n",ans);
	return 0;
}

---

The End

Thanks for reading!