[AGC043D] Merge Triplets

做法

容易发现一个排列可行的充要条件是,把每个前缀极大值到下一个前缀极大值之前(不包括)的元素划到一段,每段长度都不超过 \(3\),且长为 \(1\) 的段数大于等于长为 \(2\) 的段数。

\(f_{ij}\) 表示一个 \(1\ldots i\) 的排列,按上述方式划分段后,每段长度不超过 \(3\),且长为 \(2\) 的段数减去长为 \(1\) 的段数为 \(j\)

考虑决定元素 \(n\) 的位置,之后左右的部分是独立的,即可得到转移:

\[ f_{i,j} = 0!\binom{i-1+0}{0}f_{i-1,j+1}+1!\binom{i-2+1}{1}f_{i-2,j-1}+2!\binom{i-3+2}2f_{i-3,j} \\=f_{i-1,j+1} + (i-1)f_{i-2,j-1} + (i-1)(i-2) f_{i-3,j} \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
int n, mod;

int f[4][maxn * 6];

int main() {
scanf("%d%d", &n, &mod);
n *= 3;
f[0][n] = 1 % mod;
for (int i = 1; i <= n; i++) {
int l0 = (i-1+4)%4, l1 = (i-2+4)%4, l2 = (i-3+4)%4;
int l = i % 4;
for (int j = 0; j <= 2*n; j++) {
f[l][j] = f[l0][j+1];
if (i >= 2 && j) f[l][j] = (f[l][j] + 1LL * (i-1) * f[l1][j-1]) % mod;
if (i >= 3) f[l][j] = (f[l][j] + 1LL * (i-1) * (i-2) * f[l2][j]) % mod;
}
}
int ans = 0;
for (int i = 0; i <= n; i++) ans = (ans + f[n%4][i]) % mod;
printf("%d\n", ans);
return 0;
}