题解：P3867 [TJOI2009] 排列计数

yyyx_ · 2025-12-05 09:48:38 · 题解

求邻项差 \le k 的 n 的排列数量。

考虑一个经典的连续段 trick：从 1\sim n 向排列中插入数字，维护共有多少段连续段。每次操作形如：

1. 新建一个段。
2. 拼在原有的段的左右。
3. 将两个相邻的段用一个数字拼起来。

具体见CF1515E。

发现这道题也可以这样刻画，并且我们只关心段两端的数的值。容易想到直接维护当前所有段的左右端点值。这道题分四种情况：最终序列中，左右端点都不确定，左端点确定，右端点确定，左右端点都确定。发现每种情况的连续段的形态都是固定的，可以直接用一个 \mathcal{O}(k) 的序列来刻画。然后你发现状态数是 \mathcal{O}(k!) 的。

所有可转移的状态用 vector 储存即可，转移 \mathcal{O}(k) 是平凡的。共 n 次插入数字，总复杂度 \mathcal{O}(nk\times k!)。这算爆标了吗。