题目传送门
这道题是一道$DP$题，思维难度比较大。
题意：先定义波形数组：满足当$i$全为奇数或偶数时，$a[i]>a[i-1]$且$a[i]>a[i+1]$。
求$n$的全排列中有多少个符合波形数组。
想法是：如果第$i$个数是山峰，下一个肯定是山谷，也就是说要从剩下的且比第$i$个数小的数中挑到第$i+1$个数中。反之要挑大的数。
我们记录状态为$f[i][j][0/1]$，$i$为剩下$i$个数，$j$表示有$j-1$个数小于刚刚选择的数，当第$3$个下标为$0$时，表示这是山谷，为$1$则说明是山顶。
推理知道$f[i][j][0]$能影响$f[i-1][j..i][1]$，$f[i][j][1]$能影响$f[i-1][1..j-1][0]$。
初始化为$f[n][0][0]=f[n][n+1][1]=1$，其他为$0$。原因在于：刚开始所有数都可以作为第一个数为山峰或山谷，要么没有数比上一层大，要么所有数比上一层都大。
最后求$f[0][1][0]+f[0][1][1]$的值即可。
此时时间复杂度为$O(n^3)$，空间为$O(n^3)$。
但是过不了。。
考虑将转移方程变化下，把刷表改成填表，就发现$f[i][j][1]=sum_{x=0}^jf[i+1][x][0]$，$f[i][j][0]=sum_{x=j+2}^{i+2}f[i+1][x][1]$，然后又发现可以在填表的过程中顺便求下$Sigma$，于是就优化到了$O(n^2)$。
而空间可以通过滚动数组优化掉一维。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define repd(i, a, b) for (re int i = a; i >= b; --i) 8 #define maxx(a, b) a = max(a, b); 9 #define minn(a, b) a = min(a, b); 10 #define LL long long 11 #define inf (1 << 30) 12 13 inline int read() { 14 int w = 0, f = 1; char c = getchar(); 15 while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); 16 while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar(); 17 return w * f; 18 } 19 20 const int maxn = 4200 + 10; 21 22 int f[2][maxn][2], n, P, cur = 1; 23 24 int main() { 25 n = read(), P = read(); 26 27 memset(f, 0, sizeof(f)); 28 29 f[cur][0][0] = f[cur][n+1][1] = 1; 30 31 repd(i, n-1, 0) { 32 cur ^= 1; 33 rep(j, 0, i+2) f[cur][j][0] = f[cur][j][1] = 0; 34 int v = f[cur^1][0][0]; 35 rep(j, 1, i+1) { 36 v = (v + f[cur^1][j][0]) % P; 37 f[cur][j][1] = (f[cur][j][1] + v) % P; 38 } 39 v = f[cur^1][i+2][1]; 40 repd(j, i+1, 1) { 41 f[cur][j][0] = (f[cur][j][0] + v) % P; 42 v = (v + f[cur^1][j][1]) % P; 43 } 44 } 45 46 printf("%d", (f[cur][1][0] + f[cur][1][1]) % P); 47 48 return 0; 49 }
这道题还可以用数学统计下手推方程。