DP、计数（1，但是没有 2）

Stairs

定义一个排列 \(p\) 的阶梯序列为 \(a\)，其中 \(a_i\) 为“包含 \(p_i\) 的连续段的长度最大值，满足该连续段是一个仅由连续自然数组成的递增或递减段”。

给定阶梯序列 \(a\)，求合法的 \(p\) 数量。

\(n \le 10^5, 1\le a_i \le n\)。

下称 阶梯段 为 仅由连续自然数组成的递增或递减连续段。

原序列可以划分为若干个极长阶梯段。阶梯序列中存在若干连续段，段内值相同，可以发现，划分的阶梯段每段长与阶梯序列直接对应，可以求出 \(b_{1,\dots,m}\) 表示第 \(i\) 个极长阶梯段的长为 \(b_i\)。

考虑 dp。有一个限制“极长”：相邻阶梯段不能合并为一个更大的阶梯段，不容易直接维护。但是这是可以容斥的。定义 \(f_{i,j}\) 表示前 \(i\) 个阶梯段，但是可以将其合并为至少 \(j\) 个阶梯段（也就是说，钦定将 \(i\) 个阶梯段合并 \(i-j\) 次）的方案数。答案即为 \(\displaystyle\sum_{j=1}^m (-1)^{m-j}j!f_{m, j}\).（先划分有序自然数列，通过 \(j!\) 任意排列阶梯段对应的首个数的大小）。

注意到 \(b_i=1\) 是特殊的，若其单独成段，则无法通过反转得到新方案，其他的均可反转 \(\times 2\)：

\[f_{i,j}=\begin{cases} f_{i-1,j-1}+\displaystyle 2\sum _{k=0}^{i-2}f_{k,j-1} & b_i=1\\ \displaystyle 2\sum _{k=0}^{i-1}f_{k, i}&b_i > 1\\ \end{cases} \]

定义 \(f_{i,j}\) 生成函数：\(F_i=\displaystyle\sum_{j=0}^{i-1} f_{i,j+1}x^j\)，定义 \(S_i=\displaystyle\sum _{j=0}^iF_j\)。转移可写作：

\[F_i = \begin{cases} xF_{i-1}+2xS_{i-2} & b_i=1\\ 2xS_{i-1}=2xF_{i-1}+2xS_{i-2} & b_i > 1 \end{cases} \]

可以写作若干个 \(2\times 2\) 的多项式矩阵乘积，依据分配律大力分治 FFT 就可以做到 \(O(n \log^2n)\)。

其实也不难（?）