「问题描述」

czy有很多妹子，妹子虽然数量很多，但是质量不容乐观，她们的美丽值全部为负数（喜闻乐见）。

czy每天都要带N个妹子到机房，她们都有一个独一无二的美丽值，美丽值为-1到-N之间的整数。他想要把这些妹子排成一个波动序列，这样相对“漂亮”（美丽值的绝对值较小）的妹子可以与她旁边的两个美丽值的绝对值较大的妹子形成鲜明的对比，整个序列相对将更加“美观”（不再那么无法直视）。

一个序列是波动序列仅当序列中的每个数比周围的两个数都大或都小（如果有的话）。

现在czy希望知道，长度为N的波动序列有多少种。两种序列A和B不同当且仅当存在一个i，使得Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

「输入格式」

输入文件czy.in仅含一行，两个正整数N, P。

「输出格式」

输出文件czy.out仅含一行，一个非负整数，表示你所求的答案对P取余之后的结果。

「样例输入输出」

czy.in

4 7

czy.out

3

说明：共有10种可能的序列，它们是：  1324 1423 2143 2314 2413  3142 3241 3412 4132 4231

(忽略负号)

「数据规模和约定」

对于20%的数据，满足N≤10；

对于40%的数据，满足N≤18；

对于70%的数据，满足N≤550；

对于100%的数据，满足3≤N≤4200，P≤10^9。

「题解」

本题改编自地精部落

wulala：

f[i][j]第一位为[1,j]且第一位下降的1~i的合法排列数,先给出结论:f[i][j] = f[i][j – 1] + f[i – 1][i – j]
首先是要加上[1,j – 1]的合法排列数,然后考虑j开头的第一位下降合法排列数
这个就是求以[1,j]开头的1~n-1的第一位上升合法排列数(这个应该可以YY一下吧..)
但是第一位上升的合法排列数我们是没有算的,但注意到第一位上升和第一位下降具有对称性
所以求以[1,j]开头的1~n-1的第一位上升合法排列数就是f[i – 1][i – j]
然后如果开[4200][4200]的int的话正好会被卡掉,所以必须滚动数组..