题解

思路

排列中的最大元素 $N$ 一定会被两个方向各记录一次。把它删除后，左侧元素只影响左侧记录数，右侧元素只影响右侧记录数。这个分解可以用第一类无符号斯特林数合并成一个闭式。

做法

子任务 1：枚举排列

枚举 $N!$ 个排列，分别从两端扫描并统计记录次数。复杂度为 $O(N!N)$。

子任务 2：斯特林数动态规划

第一类无符号斯特林数 $c(n,k)$ 满足

$$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k).$$

固定最大元素左边有 $l$ 个数。选择这些数有 $\binom{N-1}{l}$ 种；左半排列需要 $A-1$ 个从左记录，右半排列需要 $B-1$ 个从右记录。因此答案为

$$\sum_{l=0}^{N-1}\binom{N-1}{l}c(l,A-1)c(N-1-l,B-1).$$

斯特林数的标号循环解释说明，这个卷积等于

$$c(N-1,A+B-2)\binom{A+B-2}{A-1}.$$

直观地说，先把 $N-1$ 个元素组织成 $A+B-2$ 个循环，再从这些循环中选 $A-1$ 个标记为最大元素左侧贡献，其余标记为右侧贡献。

当 $N\le5000$ 时，用上述递推计算目标行中所需的 $c(N-1,A+B-2)$，复杂度为 $O(N(A+B))$，空间复杂度为 $O(A+B)$。

子任务 3：多项式乘积与 NTT

第一类无符号斯特林数还是升幂多项式的系数：

$$\prod_{i=0}^{N-2}(x+i)=\sum_k c(N-1,k)x^k.$$

用分治把所有一次多项式相乘。模数 $998244353$ 支持快速数论变换，每次卷积使用 NTT；得到目标系数后再乘组合数即可。

若 $A=0$、$B=0$ 或 $A+B-2>N-1$，答案显然为零。其余情况下用阶乘和逆阶乘计算组合数。

复杂度

三个层级的复杂度分别为 $O(N!N)$、$O(N(A+B))$ 和 $O(N\log^2N)$；满分算法空间复杂度为 $O(N\log N)$ 的分治临时多项式总峰值，实际同时存活规模为 $O(N)$。

正确性

最大元素把排列唯一分成左右两部分，且自身分别贡献一次记录。固定左侧元素集合后，两部分内部记录数分别由第一类无符号斯特林数计数，因此得到卷积式。循环染色双射把卷积合并为一个斯特林数乘组合数。NTT 只改变计算多项式乘法的方法，不改变系数，所以最终输出恰为所有合法排列数。