读题
可以发现，需要山峰山谷相接的山脉。例如：$1423$,$2143$。
乍一看并没有什么头绪。所以需要亿个小小的表。
打表
3位数： 4位数：
(先峰) (先谷) (先峰) (先谷)
山峰 山谷 山峰 山谷
132 1324
213 231 1423
312 2314 2134
2413
3412 3142
3241
4132
4231
找规律
- 所有的山峰情况让 $n+1$ 减每一位可以得到所有的山谷情况，所以要计算总和只用求出先锋或先谷全部情况在 $\times2$ 即可
- $n$ 位数的情况皆可以有 $n-1$ 位数的情况推出来。例如：$1324$，$1423$。可以分成 $1$—$324$，和 $1$—$423$。现在我们将 $324$ 和 $423$ 看成三位数，合法化后就是 $213$ 和 $312$。
这里说的合法化就是 $n$ 位数有 $1$~$n$ 组成的峰谷相连的数列，例如 $324$ 的合法化：$324$ 是三位数，应由 $1$，$2$，$3$ 组成，所以合法化后就是 $213$，符合峰谷相连，且山脉大致形状不变（左峰比右峰低）
这不就是 $3$ 位数中先峰的情况之和么。再比如：$2143$,$2314$,$2413$.可以分成两类：
- 第一类是 $2143$（先峰）；
- 第二类是 $2314$,$2413$（先谷）。
- 先山峰：$2143$ 可分成 $2$—$143$。$143$ 合法化后就是 $132$.可以发现同样是 $3$ 位数情况里的第一个。至于为什么没有合法化后是 $231$（同样是先谷山脉）在后面说明
- 先山谷：$2$—$314$，$2$—$413$ 合法化后是 $213$ 和 $312$.也都是 $3$ 位数中先山峰的情况。
- 如果将 $4$ 位数中 $3$ 开头的情况也打出来会发现：与 $2$ 开头的情况恰好相反。即：$3$—$412$ 合法化后是 $312$，没有 $213$ 的情况。想想为什么？
思考
现在假如有以 $2$ 开头的 $4$ 位数，后三位合法化后是 $231$ 的情况。现在我们要逆推一下，这个 $4$ 位数如果合法是什么。
$2$—$231$。不能存在两个 $2$，所以要做一些操作。
- 首先，既然选了 $3$ 位数中的先山谷，那几一定要比前面的开头数小。
- 所以只能将 $231$ 中的 $2$ 缩小，缩小后又与原来的 $1$ 冲突。
- 现在就只能放弃或改变山峰的形状了（不再是左谷比右谷高的山脉特点）。
事实证明，不存在 $2$—$231$ 的合法山脉
同样 $3$—$213$ 同样不存在（证明方法相似，不再赘述）
规律
现在将打的表整理一下：
n=3 n=4 n=5
序列开头数字 先锋 先谷 先锋 先谷 先锋 先谷
1: 0 1 0 2 0 5
2: 1 1 1 2 2 5
3: 1 0 2 1 4 4
4: 2 0 5 2
5: 5 0 由上面的推论和图可以发现递推规律：
设$g_i[n]$为输入$i$时的山谷，设$f_i[n]$为输入的$i$时的山峰。
拿$i=4$举例
$g_4[0]=f_3[0]+f_3[1]+f_3[2]+f_3[3]$
$g_4[1]=f_3[1]+f_3[2]+f_3[3]$
$g_4[2]=f_3[2]+f_3[3]$
$g_4[3]=f_3[3]$
$ans=g_4[0]+g_4[1]+g_4[2]+g_4[3];$
$ans*=2;$//山峰和山谷情况一样多
运算时记得及时取模
前缀和
用我们发现的规律每回都求一次和，显然会TLE。。。别问我是怎么知道的
所以我们需要一种更快的方式来加和，仔细观察上面的规律中的公式，反过来看不就是一个前缀和么！！所以完全可以倒序计算存储。
代码
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long n,p;
long long now_xvlie[10001];\\当前序列，存先锋
long long nest_xvlie[10001];\\ 前缀和，也是下一个序列倒序，即下一个序列先谷
void update(int n){\\更新下一个序列，即求当前序列的前缀和
nest_xvlie[0]=0;
for(int i=1;i<n;i++){
(nest_xvlie[i]=nest_xvlie[i-1]+now_xvlie[i-1])%=p;
}
}
void gai(int n){\\更改当前序列，递推出下一个序列
update(n);
for(int i=0;i<n;i++){
now_xvlie[i]=nest_xvlie[n-i-1];\\逆序存储
}
}
void out(int n){\\输出
long long ans=0;
for(int i=0;i<=n;i++)
ans=(ans+now_xvlie[i])%p;
cout<<(ans*2)%p<<endl;
}
int main(){
cin>>n>>p;
now_xvlie[0]=1;now_xvlie[1]=1;\\初始化，注意n>=3
for(int i=3;i<n;i++){\\从 3 开始
gai(i+1);
}
out(n);
return 0;
} 代码
这个代码可以看到从 $3$ 到 $n$ 的先锋和先谷顺序以及总和（注意数据范围）。
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long n,p;
long long now_xvlie[10001];
long long next_xvlie[10001];
void out(int n){
long long ans=0;
for(int i=0;i<=n;i++)
ans=(ans+now_xvlie[i])%p;
cout<<" total:"<<(ans*2)%p<<endl;
cout<<endl;
}
void update(int n){
next_xvlie[0]=0;
cout<<" next_xvlie:"<<next_xvlie[0]<<" ";
for(int i=1;i<n;i++){
(next_xvlie[i]=next_xvlie[i-1]+now_xvlie[i-1])%=p;
cout<<next_xvlie[i]<<" ";
}
cout<<endl;
}
void gai(int n){
cout<<" n="<<n<<endl;
update(n);
cout<<" now_xvlie:"<<" ";
for(int i=0;i<n;i++){
now_xvlie[i]=next_xvlie[n-i-1];
cout<<now_xvlie[i]<<" ";
}
cout<<endl;
out(n);
}
int main(){
cin>>n>>p;
now_xvlie[0]=1;now_xvlie[1]=1;
next_xvlie[1]=1;next_xvlie[2]=1;
cout<<" n=3"<<endl;
cout<<" next_xvlie:"<<next_xvlie[0]<<" "<<next_xvlie[1]<<" "<<next_xvlie[2]<<endl;
cout<<" now_xvlie: "<<now_xvlie[0]<<" "<<now_xvlie[1]<<" "<<now_xvlie[2]<<endl;
out(3);
cout<<endl;
for(int i=3;i<n;i++){
gai(i+1);
}
cout<<endl<<endl;
out(n);
return 0;
} 
