求长度 \(n\) 的交错序列的方案数。
思路
长度为 \(i\) 的序列对于长度为 \(i-1\) 的序列来说多了最大值 \(i\) ，所有我们可以枚举这个最大值的位置
为保证是交错序列，那么最大值位置的前驱和后继都必须是“山谷”
从最大值的位置 \(j\) 劈开，问题该状态便可以转化成两个子状态：
长度为 \(j\) 的结尾下降的序列方案数和长度为 \(i-1-j\) 的开头上升的序列方案数
结尾下降和开头上升本质相同
最后方案数要乘上组合 \(C_{i-1}^j\) （从 1 至 \(i-1\) 中选出 \(j\) 个数组成最大值前面的序列，离散化后方案数相同）
状态表示 & 转移方程
设 f[i]表示长度为 \(i\) 的交错序列的方案数
显然，开头上升和开头下降的方案一样多，开头上升的方案数就是总方案数的一半
\[ \large f[i] = \sum_{j=0}^{i-1}\frac{f[j]}{2}\cdot\frac{f[i-1-j]}{2}\cdot C_{i-1}^{j} \]
细节
边界
f[1] = 1，除以2不就。。。
其实长度为1的序列可以看成两种情况（“山谷”或“山峰”）
至于f[0]，当序列最大值置于最左侧（\(j=0\)）时方案数不能乘0啊
所以f[0] = f[1] = 2
取模
问题来了，\(p\) 不为质数，不能求2的逆元，且 \(a=b\ (mod\ p)\) 不等价于 \(\frac{a}{2}=\frac{b}{2}\ (mod\ p)\)
怎样除以 2 ？
因为 \(x\ mod\ p=(x\ mod\ 2p)\ mod\ p\) （ \(x\) 为 \(mod\ 2p\) 意义下的偶数）
所以 \(\frac{x}{2}\ mod\ p=(\frac{x\ mod\ 2p}{2})\ mod\ p\)
过程中模 \(2p\) 的意义下随便除以2，最后再模 \(p\) 输出即可
空间
似乎、听说、大概递推组合数的数组空间开不下，滚呗
code
1 | read(n), read(p); |