Description
传送门
求(N)的排列中有多少个波动数列.
波动数列是指对于数列中的每一个数,他两边的数必须严格小于或大于自己.
[n leq 4200, Mod leq 1e9
]
Solution
首先我们必须要搞清楚3个性质
- First: 在一个波动数列中，若两个 i 与 i+1 不相邻，那么我们直接交换这两个数字就可以组成一个新的波动数列； 举个栗子： 5 2 3 1 4
4 2 3 1 5
- Second: 把波动数列中的每个数字Ai 变成 (N+1)-Ai 会得到另一个波动数列，且新数列的山峰与山谷情况相反；
举个栗子： 1 4 2 5 3 （用 6 - 每个数） 1是山谷，4是山峰，后面类推
5 2 4 1 3 这个数列也是波动的 ，且 5是山峰，2是山谷；
- Third: 波动序列有对称性。 栗子：1 4 2 5 3 to 3 5 2 1 4
(以上转自luogu)
那么我们设(Dp[i][j])表示(1)到(i)的排列中, 当前数列首端为高度j的山峰的方案数.
考虑如果j,j - 1不相邻, 那么直接交换就可以.即(Dp[i][j - 1])
如果相邻, 那么显然j - 1是山谷. 所以应用性质二,把山峰变成山谷,即:(DP[i - 1][(i - 1 + 1) - (j - 1)] = DP[i - 1][i - j + 1])
所以答案为:(DP[i][j] = DP[i][j - 1] + DP[i - 1][i - j + 1])
由于空间太小, 考虑滚动数组优化.
Codes
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s
", __LINE__, __FUNCTION__, s)
typedef long long LL;
typedef long double LD;
const int BUF_SIZE = (int)1e6 + 10;
struct fastIO {
char buf[BUF_SIZE], buf1[BUF_SIZE];
int cur, cur1;
FILE *in, *out;
fastIO() {
cur = BUF_SIZE, in = stdin, out = stdout;
cur1 = 0;
}
inline char getchar() {
if(cur == BUF_SIZE) fread(buf, BUF_SIZE, 1, in), cur = 0;
return *(buf + (cur++));
}
inline void putchar(char ch) {
*(buf1 + (cur1++)) = ch;
if (cur1 == BUF_SIZE) fwrite(buf1, BUF_SIZE, 1, out), cur1 = 0;
}
inline int flush() {
if (cur1 > 0) fwrite(buf1, cur1, 1, out);
return cur1 = 0;
}
}IO;
#define getchar IO.getchar
#define putchar IO.putchar
int read() {
char ch = getchar();
int x = 0, flag = 1;
for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;
for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
void putString(char s[], char EndChar = '
') {
rep(i, 0, strlen(s) - 1) putchar(*(s + i));
if(~EndChar) putchar(EndChar);
}
#define Maxn 4209
int n, p, dp[2][Maxn];
namespace INIT {
void Main() {
n = read(), p = read();
}
}
namespace SOLVE {
void Main() {
dp[1][1] = 1;
rep(i, 2, n)
rep(j, 1, i)
dp[i & 1][j] = (dp[(i - 1) & 1][i - j + 1] + dp[i & 1][j - 1]) % p;
int ans = 0;
rep(i, 1, n) ans = (ans + dp[n & 1][i]) % p;
ans = ans * 2 % p;
write(ans), putchar('
');
}
}
int main() {
#ifdef Qrsikno
freopen("BZOJ1925.in", "r", stdin);
freopen("BZOJ1925.out", "w", stdout);
#endif
INIT :: Main();
SOLVE :: Main();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return IO.flush();
}