题目大意
给出$n$, $p$, 求有多少长度为$n$的排列可以被分成三个上升子序列, 数量对$p$取模,
数据范围 $3 \leq n \leq 500$.
思路
首先让我们考虑如果有一个排列,如何判断这个排列合法,我可以考虑贪心,维护三个上升序列的末尾(最大值),从左到右依次将数插入序列,把这个数贪心的加到它可以加入的末尾的数最大的序列里.
因此考虑dp,定义$f[i][j][k]$表示现在有$i$个数,形成了三个上升子序列,其中最大的子序列末尾显然是第$i$大的数,第二大的子序列末尾是第$j$大的数,第三大的子序列末尾是第$k$大的数,这样的序列的数量,显然,这样枚举是不会重复的,转移的时候,考虑在这个序列末尾加数,考虑加的这个数在这$i$个数中的相对位置,设这个位置为$l$,有
$$
f[i][j][k] \rightarrow f[i+1][j][k],l=i+1 \
f[i][j][k] \rightarrow f[i+1][l][k],j < l \leq i \
f[i][j][k] \rightarrow f[i+1][j+1][l], k < l \leq j
$$
一个简单的$O(n^4)$dp
#define add(x, y) x = (x + y >= md) ? x + y - md : x + y
f[1][0][0] = 1;
for (int i = 1; i < n; ++i)
for (int j = 0; j < i; ++j)
for (int k = 0; k <= j; ++k)
if (f[i][j][k] > 0) {
int x = f[i][j][k];
for (int l = k + 1; l <= j; ++l)
add(f[i + 1][j + 1][l], x);
for (int l = j + 1; l <= i; ++l)
add(f[i + 1][l][k], x);
add(f[i + 1][j][k], x);
}
考虑优化,发现转移的都是一段,随便前缀和搞一搞就可以了
#define add(x, y) x = (x + y >= md) ? x + y - md : x + y
#define sub(x, y) x = (x - y < 0) ? x - y + md : x - y
f[1][0][0] = 1;
for (int i = 1; i < n; ++i) {
int cur = i & 1, nxt = cur ^ 1;
memset(f[nxt], 0, sizeof(f[nxt]));
memset(tag1, 0, sizeof(tag1));
memset(tag2, 0, sizeof(tag2));
for (int j = 0; j < i; ++j)
for (int k = 0; k <= j; ++k)
if (f[cur][j][k] > 0) {
int x = f[cur][j][k];
add(tag1[j + 1][k + 1], x);
sub(tag1[j + 1][j + 1], x);
add(tag2[j + 1][k], x);
sub(tag2[i + 1][k], x);
add(f[nxt][j][k], x);
}
for (int j = 0; j <= i; ++j)
for (int k = 1; k <= i; ++k)
add(tag1[j][k], tag1[j][k - 1]), add(tag2[k][j], tag2[k - 1][j]);
for (int j = 0; j <= i; ++j)
for (int k = 0; k <= j; ++k) {
add(f[nxt][j][k], tag1[j][k]);
add(f[nxt][j][k], tag2[j][k]);
}
}
复杂度$O(n^4)$.