传送门:https://www.luogu.org/problemnew/show/P2467
参考与学习：https://www.luogu.org/blog/user55639/solution-p2467
题意：
求波动数列
思路：
设dp【i】【j】 表示长度为i， 开始位子为j， 且开始位子是波峰。
首先这个波动数列有一些性质：
1: 在一个波动数列中，若两个 i 与 i+1 不相邻，那么我们直接交换这两个数字就可以组成一个新的波动数列； 举个栗子： 5 2 3 1 4
2: 把波动数列中的每个数字Ai 变成 (N+1)-Ai 会得到另一个波动数列，且新数列的山峰与山谷情况相反；
3: 波动序列有对称性。 栗子：1 4 2 5 3 to 3 5 2 1 4
由此可以得到动态规划的递推式：
dp【i】【j】 = dp【i】【j-1】+ dp【i-1】【（ i - 1 + 1） - j + 1 】
其中，因为 i 和 i+1不相邻，所以可以互换， dp【i】【j】 += dp【i】【j-1】。
或者从 dp【i-1】【j-1】 翻转后推过来，就是dp【i-1】【（i-1+1）- j + 1】。
可以用滚动数组优化
#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue typedef long long ll; typedef unsigned long long ull; //typedef __int128 bll; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3; typedef pair<ll,int>pli; //priority_queue<int> q;//这是一个大根堆q //priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q #define fi first #define se second //#define endl ' ' #define OKC ios::sync_with_stdio(false);cin.tie(0) #define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) #define max3(a,b,c) max(max(a,b), c); #define min3(a,b,c) min(min(a,b), c); //priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+9; const double esp = 1e-8; const double PI=acos(-1.0); const double PHI=0.61803399; //黄金分割点 const double tPHI=0.38196601; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /*-----------------------showtime----------------------*/ const int maxn = 15009; ll dp[3][maxn]; int main(){ // freopen("goblin.in", "r", stdin); // freopen("goblin.out", "w", stdout); int n,p; scanf("%d%d", &n, &p); int id = 0; if(n == 3) cout<<4 % p<<endl; else { dp[id][1] = 0; dp[id][2] = 1; dp[id][3] = 1; for(int i=4; i<=n; i++){ for(int j=2; j<=i; j++){ dp[id^1][j] = (dp[id^1][j-1] + dp[id][i - j + 1])%p; } id = id ^ 1; } ll ans = 0; for(int i=2; i<=n; i++) ans =(ans + dp[id][i])% p; printf("%lld ", ans * 2 % p); } return 0; }