题解

思路

把排列看成排列矩阵。令 $d_i=i-a_i$，它表示前 $i$ 个位置中填入大于 $i$ 的数的个数，也等于位置在 $i$ 之后且值不超过 $i$ 的数的个数。因而 $d_i$ 是扫描对角线时的开放匹配数。

做法

从高度 $h$ 处处理新下标时，开放匹配数只能变为 $h+1,h,h-1$，对应方案系数分别为

$$1,qquad 2h+1,qquad h^2.$$

所以问题等价于对一条带权 Motzkin 路径计数。已知条件 $a_i\ne-1$ 就是固定路径在时刻 $i$ 的高度 $d_i=i-a_i$。

对两个相邻的已知点，设间隔长度为 $L$，起终高度为 $x,y$，记 $d=y-x$。直接对区块内的旧开放行、旧开放列和内部匹配分类，可得转移系数

$$(L!)^2\sum_{r,s} \binom{x}{r}\binom{x}{s} \frac1{(L-d-r-s)!(d+r)!(d+s)!}.$$

令 $P_r=\binom{x}{r}/(d+r)!$，双重和中固定 $r+s$ 的部分正是多项式 $P$ 与自身的卷积。用 NTT 计算每个未知区间的卷积，再乘起来即得答案。各区间长度之和为 $n$，故总复杂度可控。

子任务 1 直接枚举排列。子任务 2 直接用三对角转移做 $O(n^2)$ 的高度动态规划。

复杂度

满分算法时间复杂度为 $O(n\log n)$ 级别（分段 NTT 的总长度为 $O(n)$），空间复杂度为 $O(n)$。