Luogu5825 排列计数

题意：记 有 个升高的，长度为 的排列的个数。

给出 ，求 。

答案对 取模，，时限 。

---

设 为长度为 的排列钦定 个位置上升的填写方案数，二项式反演即可得到“恰好 个位置上升的方案数”。

考虑已经钦定好某种升高情况后，填写方案数是多少。

我们把相邻的上升连续段并在一起，称作一个块，这些元素由小于号串在一起，只能有一种排列方式（而非阶乘种）。这就能写出单个块的 EGF 。(大小为 的块不应存在)

在 中，我们对原来孤立的 个块合并了 次，所以得到 个块（记为 ）。

要得到 个块，计算 即可。我们需要的是块大小和为 的贡献和，所以欲求 。

这是加法卷积的形式。得到所需的 后二项式反演，复杂度 。

进一步化简可以得到一次卷积的公式，具体结果略。