没用滚动数组瞎写居然没有被卡空间！！！！

这题在省选题里还是算比较简单的
蒟蒻第一次写题解

---

题意分析

首先我们根据题意

·这N段山脉每段都可以修建瞭望台或酒馆的其中之一

就是要求长度为n的上下滚动的数组数量，例如

（n=5) 1 4 2 5 3

就是一组。

---

方法分析

冥思苦想两分钟好像并没有此类公式...偷懒失败~

很容易想到用dp，我们用f ( i , j )表示当 n = i 时，以j为开头的方案数量

我们不妨设第一个j是山峰（由对称性最后ans*2即可）

先上转移方程（递推公式）

f(i,j)=f(i,j-1)+f(i-1,i-j+1)

接下来解释为什么
考察j与j-1的位置关系

1. 若j与j-1不相邻
   互换j与j-1，仍然得到的是一族合法的序列，且以j-1开头。具体为什么...自己写几个就会发现规律~
   所以 f(i,j)+=f(i,j-1)

2. 若j与j-1相邻
   这个情况复杂一些 其实只需要计算以j-1为山谷的排列数量
   山谷怎么办呢？
   想到把后面的数字全部反转，即 l --> n+1-l 不难发现得到的仍是合法序列。
   并且讨厌的山谷，变成了山峰！
   所以 f(i,j)+=(i-1,i-j+1)

我们就得到了转移方程~~~

代码欣赏

惊现邪教活动代码！

//僕らのラブライブ！サンシャイン！！
//P2467
#include<bits/stdc++.h>
using namespace std;
const int maxn=4205;
int f[maxn][maxn];
int n,mod,ans;
int main(){
    cin>>n>>mod;
    f[1][1]=1;
    f[2][2]=1; //初始条件
    for(int i=3;i<=n;i++){
        for(int j=2;j<=i;j++){
            f[i][j]=(f[i][j-1]+f[i-1][i-j+1])%mod;
        }
    }
    for(int j=2;j<=n;j++) {
        ans+=f[n][j];
        ans%=mod;  
    }
    cout<<ans*2%mod;  //别忘记模了
}