我们称一个排列是合法的，当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。
求长度为 的合法排列数量。
链接
题解
题目相当于要求 ~ 的合法排列数。
设 表示 ~ 的排列，第一个数为 （），且第二个数比第一个数小的方案数。
考虑第二个数，当第二个数小于 时，其方案数为第一个数为 时的方案数，即 。 当第二个数等于 时，从第二个数开始，是一个 ~ 的排列，这个排列的第二个数比第一个数大。如果将每个数 变成 ，那么就变成原有的第二个数比第一个数小的情况了。即 。
所以转移方程为 。
答案为 ，因为要考虑第二个数大于第一个数的方案数所以乘 。
代码
不使用滚动数组，内存 30M+ 是可以过的。
#include <cstdio>
const int MAXN = 4200;
int n, p;
int _f[MAXN * (MAXN + 1) / 2];
int *f[MAXN + 1];
inline void init() {
int *curr = _f;
for (int i = 0; i < n; i++) {
f[i] = curr;
curr += i + 1;
}
// printf("%ld %d\n", curr - _f, n * (n + 1) / 2);
}
int main() {
scanf("%d %d", &n, &p);
init();
f[1][1] = 1;
for (int i = 2; i < n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = (f[i][j - 1] + f[i - 1][i - j]) % p;
// printf("f[%d][%d] = %d\n", i, j, f[i][j]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) ans = (ans + f[n - 1][i]) % p;
printf("%d\n", ans * 2 % p);
return 0;
}
使用滚动数组之后，时间也快不少。
#include <cstdio>
const int MAXN = 4200;
int n, p;
int main() {
scanf("%d %d", &n, &p);
static int f[2][MAXN];
f[1 % 2][1] = 1;
for (int i = 2; i < n; i++) {
for (int j = 1; j <= i; j++) {
f[i % 2][j] = (f[i % 2][j - 1] + f[(i - 1) % 2][i - j]) % p;
}
}
int ans = 0;
for (int i = 0; i < n; i++) ans = (ans + f[(n - 1) % 2][i]) % p;
printf("%d\n", ans * 2 % p);
return 0;
}