题目：

题目描述

做一只明媚的兔子…
兔子都比较喜欢蹦蹦跳跳.但是蹦蹦跳跳的时候如果一直往高处跳的话就太累了,如果一直往低处跳的话就太无聊了.所以兔子希望跳的时候能够往上跳一步,往下跳一步,往上跳一步,往下跳一步….一共经过n个高度互不相同的位置(只要向上跳和向下跳相间分布就可以了,第一步可以往上跳也可以往下跳).如果下一个位置的高度比前一个位置高,就是往上跳,比前一个位置低,就是往下跳.
兔子今天又蹦蹦跳跳依次经过了n个位置.现在它想知道经过的n个位置的高度有多少种不同的可能.
我们认为n个位置的高度形成了1到n的一个排列,这个排列要么满足奇数项的高度比相邻位置都大,要么满足偶数项的高度比相邻位置都大.
n=1时,有1种可能,就是这1个位置的高度为1
n=2时,有2种可能,可以是(1,2)或(2,1)
n=3时,有4种可能,(1,3,2)(2,3,1),(2,1,3),(3,1,2)
答案可能很大,只需要输 出答案对mod取模的结果.

输入

一行两个整数n,mod

输出

一行一个整数ans,表示所有可能的排列数目对mod取模后的结果.

样例输入

3 1000000007

样例输出

4

提示

5<=n<=2000

对于所有测试点，mod在int范围内

思路：

  首先奇和偶的方案数肯定是一样的，所以我们只需要考虑其中一种计算即可。答案乘2即可。$dp[i][j]$表示第i个数选j的方案数， 如果当前上升的话则可从$dp[i-1][j - 1，j-2…]$等转移过来，下降反之。现在考虑j在之前有没有出现过。假设$j == i$那么从之前之前的转移过来肯定没问题。假设$j < i$， 那么我们只需要假想成前面$i-1$的排列大于等于$j$的全部都$++$一下，那么当前就也是一个合法的i的排列。所以不会出现重复的情况。这样是$n^3$的。
  稍微改一下dp状态，$dp[i][j]$表示第i个数选$1~j$的方案数，这样$dp[i][j] = dp[i][j-1] + dp[i-1][i-j]$，每次只考虑j这样就是$n^2$的了，相较于之前的就是一个前缀和优化。为什么是$dp[i-1][i-j]$?之前是升当前就是降， 状态总是反的。也可以说成把原来$i-1$的合法排列每个数取个反， 就可以迎合当前的j了。

实现：

#include <cstdio>
#define ll long long
ll dp[2007][2007];
int main() {
    int n, mod;
    scanf("%d%d", &n, &mod);
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][i - j]) % mod;
    printf("%lld\n", dp[n][n] * 2 % mod);
    return 0;
}