题解

思路

令 $d_{i,s}$ 表示长度为 $i$ 且 fun 值为 $s$ 的排列数。若首元素排名为 $j$，左右长度分别为 $j-1$ 与 $i-j$；选出左侧元素集合有 $\binom{i-1}{j-1}$ 种，总代价再加 $i$。

定义生成函数 $F_i(x)=\sum_s d_{i,s}x^s$，则

$$F_0=1,\quad F_i=x^i\sum_{j=1}^i\binom{i-1}{j-1}F_{j-1}F_{i-j}.$$

做法

子任务 1 枚举全部排列并直接递归模拟。子任务 2 用上述式子直接卷积系数。

满分算法注意 $\deg F_n\le D=n(n+1)/2$。在 $D+1$ 个点分别计算 $F_n(x)$：令 $H_i=F_i/i!$，二项式系数消去后有

$$H_i=\frac{x^i}{i}\sum_{j=0}^{i-1}H_jH_{i-1-j},$$

所以单点只需 $O(n^2)$。再用拉格朗日插值恢复 $F_n$ 的全部系数，最后求 $s\ge lim$ 的系数和。等距点的分母由阶乘、逆阶乘 $O(1)$ 得到；公共乘积多项式除以一次因子可用合成除法线性完成。

正确性证明

按首元素排名划分时，左右子排列的相对次序独立，元素集合选择数为对应二项式系数，且当前调用恰贡献 $i$，故生成函数递推逐项精确计数。除以阶乘只是代数等价变形。$F_n$ 次数不超过 $D$，因此 $D+1$ 个互异点唯一确定它；拉格朗日恢复的各系数正是 $d_{n,s}$，尾和即题目答案。

复杂度分析

满分算法时间复杂度 $O(n^4)$，空间复杂度 $O(n^2)$。