题目传送门
题意：有 1∼3n 的正整数，不重不漏地划分到 n 个栈内，每个栈有 3 个元素。每次从所有栈顶中选择最小的元素取出，直至取完，每次取的元素生成了一个 1∼3n 的排列，求该排列的方案数。
考虑排列应该长什么样。从左往右考虑不好考虑，因为没法确定一开始选什么元素，所以可以从右往左考虑。注意到，最大的元素 3n 一定只会在没有别的栈顶可选的时候才会选，此时只剩一个栈，栈顶为 3n。选完 3n 后，栈中剩下的 0∼2 个元素一定都会依次选完。所以，元素 3n 和剩下的 0∼2 个其他元素一定会出现在排列的末尾。由于有 3n 阻挡，剩下的 0∼2 个元素在之前不会参与任何比较过程，所以之前的部分不需要考虑这 1∼3 个元素。在剩下的元素中再找最大值，反复这一过程即可。
一个非常重要的性质为，最大的元素 3n 后面的 0∼2 个元素是什么，对之前的方案数不会有任何影响，所以可以考虑一个 DP：f[i] 表示取到还剩 i 个元素的方案数，则 f[i]=f[i+1]+f[i+2]⋅(i+1)+f[i+3]⋅(i+1)⋅(i+2)，其中转移的系数表示被阻挡的 0∼2 个元素任意取。
这个 DP 其实是不对的，因为并不是任意分组都可以有解，还要让这些分组必须能完整地放到 n 个大小为 3 的栈内。显然大小为 3 的组（最大值搭配后面两个元素）独占一个栈，一个大小为 2 的组（最大值搭配后面一个元素）必须和一个大小为 1 的组匹配，而大小为 1 的组可以自己匹配。这就要求大小为 2 的组的数量不能超过大小为 1 的数量。于是可以记录第二维状态：f[i][j] 表示取到还剩 i 个元素，大小为 1 的组数-大小为 2 的组数等于 j 的方案数，则转移时更改一下 j 的值即可。统计答案时只计算最终状态 j≥0 的状态答案。
为了防止下标出现负数，可以往正方向平移 2n。复杂度 3n×5n=O(n2)。
By cxm1024
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
int n,mod,f[6010][15010];
signed main() {
cin>>n>>mod;
f[n*3][n*2]=1;
for(int i=n*3;i>0;i--)
for(int j=0;j<=n*5;j++) {
if(i>=3) (f[i-3][j]+=1ll*f[i][j]*(i-1)*(i-2)%mod)%=mod;
if(i>=2) (f[i-2][j-1]+=1ll*f[i][j]*(i-1)%mod)%=mod;
(f[i-1][j+1]+=f[i][j])%=mod;
}
int ans=0;
for(int i=n*2;i<=n*5;i++)
(ans+=f[0][i])%=mod;
cout<<ans<<endl;
return 0;
}
|