题解：黏液与序列（简单版）

思路

一、从好序列到欧拉数

记 $E(m,r)$ 为欧拉数：长度为 $m$ 的排列中，恰有 $r$ 个下降位置的排列数。 取约定 $E(0,0)=1$，越界时为 $0$。它满足

$$E(m,r)=(m-r)E(m-1,r-1)+(r+1)E(m-1,r).$$

对原问题作标准的插入位置计数，可以得到数字 $k$ 的总出现次数为

$$\operatorname{Ans}_n(k)=n!\sum_{m=k}^{n}\frac{E(m,k-1)}{m!}.$$

因此只需逐行计算欧拉数，并把第 $m$ 行按 $1/m!$ 加入答案。

做法

二、子任务 1：直接枚举

当 $n\le7$ 时，枚举所有 $n^n$ 个取值在 $[1,n]$ 的序列。对每个出现的 $k>1$，检查是否存在更早的 $k-1$；合法时累计各值出现次数。

复杂度为 $O(n^{n+2})$，只适用于第一个子任务。

三、子任务 2：容斥计算欧拉数

欧拉数也有显式公式

$$E(m,k-1)=\sum_{t=0}^{k}(-1)^t\binom{m+1}{t}(k-t)^m.$$

预处理组合数和阶乘后，按公式计算每个 $E(m,k-1)$，再代入答案式。直接实现的 复杂度为 $O(n^3\log n)$，空间复杂度为 $O(n^2)$，可通过 $n\le180$。

四、满分算法：滚动欧拉数 DP

令 dp[k] 表示当前行的 $E(m,k-1)$。从上一行转移到长度 $m$ 时：

$$\text{ndp}[k]=(m-k+1)\text{dp}[k-1]+k\text{dp}[k].$$

每得到一行，就执行

$$S_k\mathrel{+}=\text{dp}[k]\cdot (m!)^{-1}.$$

最后输出 $S_k\cdot n!$。所有运算均在模 $998244353$ 下进行，逆阶乘由费马小定理 预处理。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

复杂度

• 子任务 1：$O(n^{n+2})$ 时间，$O(n)$ 空间。
• 子任务 2：$O(n^3\log n)$ 时间，$O(n^2)$ 空间。
• 满分算法：$O(n^2)$ 时间，$O(n)$ 空间。

五、正确性证明

引理 1

长度为 $m$、恰有 $k-1$ 个下降位置的排列数满足上述欧拉数递推。

证明。 把最大元素插入长度为 $m-1$ 的排列。若原排列有 $k-2$ 个下降位置， 有 $m-k+1$ 个插入位置会新增一个下降；若原排列已有 $k-1$ 个下降位置，有 $k$ 个插入位置保持下降数不变。两类互斥且覆盖全部情况。证毕。

引理 2

原题数字 $k$ 的答案为 $n!\sum_{m=k}^{n}E(m,k-1)/m!$。

证明。 按决定好序列中相邻值首次/末次相对次序的有效位置集合分类。固定有效 位置数 $m$ 后，其相对次序与恰有 $k-1$ 个下降的排列一一对应，共 $E(m,k-1)$ 种；未固定的 $n-m$ 个位置可插入，贡献系数为 $n!/m!$。对所有 $m\ge k$ 求和即得结论。证毕。

定理

满分算法输出所有 $k$ 的正确答案。

证明。 由引理 1，滚动 DP 精确计算每个 $E(m,k-1)$；算法在第 $m$ 行加入 $E(m,k-1)/m!$，所以循环结束时 $S_k$ 恰为引理 2 中的和。最后乘以 $n!$，得到 所求答案。证毕。