[数学记录]AT5801 [AGC043D] Merge Triplets

**题意** ： 将 $1\sim 3n$ 划分为 $n$ 个长度为 $3$ 的栈。 用如下算法生成一个排列 $P$ : - 找出栈顶最小的（非空）栈，将栈顶加到 $P$ 的末尾，并弹栈。 问有多少排列 $P$ 可能被生成。 $n\leq 2000$ ，时限$\texttt{6s}$。 ------------ 我们发现这和归并排序类似，唯一的不同之处在于各个小序列初始时可能是无序的。 这给我们一种感觉 ： 排列 $P$ 必然是近似有序的。 显然，若各个栈初始时有序，则排列 $P$ 必然有序。接下来考虑栈中无序带来的影响。 不难发现，若栈中有一段数 $a,b,c$ 满足 $a>b,c$ （称之为“头大”段），则一定会被连续弹出。 而且，相邻两段“连续弹出”的第一次弹出是递增的。 于是，原序列被划分为了若干长度为 $1,2,3$ 的头大段，且头大段的开头递增。 观察栈中连续头大段的组成 ： $[1][1][1],[2][1],[1][2],[3]$。 又能发现，$P$ 中 $[2]$ 的个数必不多于 $[1]$ 的个数。 若满足上述两个条件，必然能构造出对应方案。 - **构造** ： 对于所有 $[3]$ 自成一栈。 对于 $[2]=\{a,b\}$ 其中 $a>b$ ，选出任一个 $[1]=\{c\}$ 与其配对成栈。 若 $c<a$ 则可以配成 $[1][2]$ ，若 $b<c$ 则可以配成 $[2][1]$ ，总能配对。 对于剩余的 $[1]$ ，三个分别排序后成一栈。 找出了充要条件，（根据数据范围）接下来使用 DP。 先考虑若已经确定段的分布，填数的方案数。约束等价为 ： 对于段 $[l,r]$ ，要求 $P_l\geq P_{1\sim r}$。 把每个段翻转，则变为要求 $P_r$ 恰组成前缀最大值。方案数为 $n!/\prod r$。 **证明** ： 考虑归纳，对于满足前 $i$ 条约束的所有排列，只有 $1/r_{i+1}$ 个满足第 $i+1$ 条约束。（离散化双射） 记 $f[i][j]$ 表示填写了前 $i$ 个数，$[1]$ 与 $[2]$ 的个数差为 $j$ 的方案数。 转移时枚举下一段为 $[1][2][3]$ 即可，乘权值分别为 $\frac{1}{(i-2)(i-1)i},\frac{1}{(i-1)i},\frac{1}{i}$ 。 为了方便，可以将 $n!$ 分配到乘权值中。 复杂度为 $O(n^2)$。 ```cpp #include<algorithm> #include<cstdio> using namespace std; int n,mod,f[6050][12050]; int main() { scanf("%d%d",&n,&mod); f[0][n]=1; for (int i=1;i<=3*n;i++) for (int j=max(0,n-i/2);j<=n+i;j++){ if (j>0)f[i][j]=f[i-1][j-1]; if (i>1)f[i][j]=(f[i][j]+1ll*f[i-2][j+1]*(i-1))%mod; if (i>2)f[i][j]=(f[i][j]+1ll*f[i-3][j]*(i-1)*(i-2))%mod; } int ans=0; for (int i=n;i<=4*n;i++) ans=(ans+f[3*n][i])%mod; printf("%d",ans); return 0; } ```