https://www.luogu.org/problem/P2467
我们需要搞到一些奇特的性质（都是在合法序列情况下的）：
性质1：当i和i+1不相邻时，交换i和i+1是一种可行的方案
性质2：给每个数都变换为n-ai+1，是一种可行方案，且山峰和山谷情况会反过来
性质3：一个合法的序列，完全翻转过来也是一个合法的序列
那么有f[i][j]表示用1~i的数字，以j作为第一个山峰
那么有方程：f[i][j]=f[i][j-1]+f[i-1][i-j+1]
各满足性质1和2，可以画图思考
最后方案数统计完之后乘二，对应性质3
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int N=4.2e3+10; int n; ll p,f[2][N],ans; int main() { scanf("%d%lld",&n,&p); f[0][2]=1; for (int i=3,q=1;i<=n;i++,q^=1) for (int j=2;j<=i;j++) f[q][j]=(f[q][j-1]+f[q^1][i-j+1])%p; for (int i=2;i<=n;i++) ans=(ans+f[n&1][i])%p; printf("%lld",ans*2%p); }
原文：https://www.cnblogs.com/mastervan/p/11367337.html
