题解

思路

由于条件与顺序无关，先把序列排序为 $x_1\le\cdots\le x_n$。若每个前缀都是好序列，则任意连续段删去较小的前缀后最小值增大、总和减小，所以仍然好；再删去中间元素也不会破坏不等式。因此只需检查所有前缀。

固定最小值后，可以按每个值出现次数计数。把排列数统一乘上 $n!$，每确定某个值出现 cnt 次就乘 $1/\text{cnt}!$，即可从多重集合恢复有序序列数。

做法

子任务 1：枚举全部序列

枚举 $(n+1)^n$ 个序列，排序后检查全部前缀，复杂度 $O((n+1)^n n\log n)$。

子任务 2：枚举最小值的计数 DP

固定最小值参数 $f$，令 $k=n+1-f$。状态 dp[used][sum][level] 表示已放入 used 个元素、累计偏移为 sum、当前处理偏移层 level 时的带阶乘权方案数。枚举当前层出现次数 cnt，乘 $1/\text{cnt}!$ 转移到下一层；前缀合法条件给出 used+cnt 的下界，且 sum+cnt*level 不超过 $f$。

对全部 $f=1,2,\ldots,n$ 求和即可。中档 $n\le40$ 时直接枚举全部最小值。

满分优化

合法排序序列满足 $x_i\ge i$；若 $x_i=i$，则前 $i$ 项必须全部等于 $i$。进一步用最小可能增长率估计可证：有贡献的最小值只可能位于

因此只需枚举 $O(\sqrt n)$ 个最小值。记忆化 DP 的维度均为 $O(n)$，每个状态枚举出现次数，足以通过 $n\le200$。

正确性说明

排序不改变子序列多重集合。所有前缀合法推出所有连续段合法，而从连续段删去中间元素只会减小右侧总和，故前缀判定等价于完美性。计数 DP 逐层枚举每个值的出现次数，used、sum 和层级下界恰好编码所有前缀约束；阶乘与逆阶乘给每个多重集合乘上准确排列数，因此无重无漏。满分算法仅删除已证明不可能产生合法序列的最小值区间，答案保持不变。

复杂度

子任务 1 为 $O((n+1)^n n\log n)$；子任务 2 枚举全部最小值；满分算法枚举 $O(\sqrt n)$ 个最小值，最坏时间复杂度 $O(n^3\sqrt n)$，空间复杂度 $O(n^3)$。