兔子都比较喜欢蹦蹦跳跳.但是蹦蹦跳跳的时候如果一直往高处跳的话就太累了如果一直往低处跳的话就太无聊了.所以兔子希望跳的时候能够往上跳一步往下跳一步往上跳一步往下跳一步....一共经过n个高度互不相同的位置(只要向上跳和向下跳相间分布就可以了第一步可以往上跳也可以往下跳).如果下一个位置的高度比前一个位置高就是往上跳比前一个位置低就是往下跳.
兔子今天又蹦蹦跳跳依次经过了n个位置.现在它想知道经过的n个位置的高度有多少种不同的可能.
我们认为n个位置的高度形成了1到n的一个排列这个排列要么满足奇数项的高度比相邻位置都大要么满足偶数项的高度比相邻位置都大.
n=1时有1种可能就是这1个位置的高度为1
n=2时有2种可能可以是(12)或(21)
答案可能很大只需要输 出答案对mod取模的结果.
一行两个整数nmod
一行一个整数ans表示所有可能的排列数目对mod取模后的结果.
首先奇和偶的方案数肯定是一样的,所以我们只需要考虑其中一种计算即可.答案乘2即可.$dp[i][j]$表示第i个数选j的方案数, 如果当前上升的话则可从$dp[i-1][j - 1,j-2...]$等转移过来,下降反之.现在考虑j在之前有没有出现过.假设$j == i$那么从之前之前的转移过来肯定没问题.假设$j < i$, 那么我们只需要假想成前面$i-1$的排列大于等于$j$的全部都$++$一下,那么当前就也是一个合法的i的排列.所以不会出现重复的情况.这样是$n^3$的.