题解

思路

把排列画成 $n\times n$ 网格中的 $n$ 个棋子：第 $i$ 行第 $p_i$ 列有一个棋子。条件等价于左上角 $i\times i$ 正方形中恰有 $a_i$ 个棋子。

从 $i-1$ 扩展到 $i$ 时，新区域是宽度为一的 L 形。设新增棋子数 $d=a_i-a_{i-1}$，枚举其中 $k$ 个落在上方矩形，其余 $d-k$ 个落在下方矩形。向一个 $h\times w$ 矩形放 $k$ 个行列互异棋子的方案数为

做法

对每个 $i$ 枚举 $k=0,\ldots,d$，将两个矩形的匹配方案数相乘后求和，再乘入总答案。若 $a_i$ 下降、超出 $i$，或最终 $a_n\ne n$，答案为零。

$n\le9$ 时可枚举所有排列核对；若恒有 $a_i=i$，唯一好排列是升序排列。

正确性说明

每一步 L 形恰是新加入左上正方形的区域。已有棋子占用的行列可以对称地视为固定，枚举上方矩形棋子数后，两块矩形中可用行列数量唯一确定。矩形匹配公式无重无漏地选择行、列及其双射。各步使用互不重叠的新行列自由度，乘法原理得到全部排列。

复杂度

简单版中相邻 $a_i$ 的可行增量至多为二，因此总时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。