Ender_hz: 记 $f_{n, m}$ 为 $n$ 元排列 $p$ 满足 $f(p)=m$ 的个数，$g_{n, k}=\sum\limits_{m=1}^{n}f_{n,m}m^k$，打表注意到递推式 $f_{n, m}=(n-1)f_{n-1, m}+f_{n-1, m-1}$，所以要求 $g_{n, 3}=\sum\limits_{m=1}^{n}f_{n, m}m^3$，用递推式展开可得 $g_{n, 3}=(n-1)g_{n-1, 3}+\sum\limits_{m=1}^{n-1}f_{n-1, m}(m+1)^3=ng_{n-1,3}+3g_{n-1,2}+3g_{n-1,1}+3g_{n-1,0}$，其他项也可以通过类似的式子得到，时间复杂度 $\mathcal O(n)$。

题解的思路大致如下：在 $n$ 给定的情况下，记随机变量 $X_i\in\{0,1\},1\le i\le n$ 为 $i$ 是否出现在一 $n$ 阶排列转化为单调栈后的序列中，则由古典概型和排列组合相关知识可知 $\mathbb E(X_i)=\mathbb P(X_i)=\dfrac{1}{i}$，同理，$\mathbb E(X_iX_j)=\dfrac{1}{ij}$，$\mathbb E(X_iX_jX_k)=\dfrac{1}{ijk}$；同时，所求结果

$$s_n=\sum\limits_{p\in\mathcal P_n} \left(\sum\limits_{i=1}^{n} X_i\right)^3=n! \mathbb E\left(\left(\sum\limits_{i=1}^{n}X_i\right)^3\right)$$

，其中

$$\left(\sum\limits_{i=1}^{n}X_i\right)^3=\sum\limits_{i=1}^{n} X_i^3 + 3\sum\limits_{1\le i, j\le n\\\,\,\,\, i\neq j} X_i^2X_j+3!\sum\limits_{1\le i<j<k\le n} X_iX_jX_k$$

，又因为 $X_i\in\{0,1\}$， 故 $X_i^k=X_i,k\in\mathbb N_+$，那么就有

$$ \left(\sum\limits_{i=1}^{n}X_i\right)^3=\sum\limits_{i=1}^{n} X_i + 6\sum\limits_{1\le i< j\le n} X_iX_j+6\sum\limits_{1\le i<j<k\le n} X_iX_jX_k $$

，即

$$ s_n=n!\mathbb E\left(\sum\limits_{i=1}^{n} X_i + 6\sum\limits_{1\le i< j\le n} X_iX_j+6\sum\limits_{1\le i<j<k\le n} X_iX_jX_k\right)=n!\left(\sum\limits_{i=1}^{n}\dfrac{1}{i}+\sum\limits_{1\le i< j\le n}\dfrac{6}{ij}+\sum\limits_{1\le i<j<k\le n}\dfrac{6}{ijk}\right) $$

，显然右侧可以通过简单的递推得到。

Ender_hz: 贡献了一发乱搞，后面 _istina_ 想出正解做法之后我实现的过程中又罚了一发。

Ender_hz: 倒推就行，就是每次考查 $A_i$ 的值在 $[x, y]$ 内时对应底数的范围 $[l, r]$，然后作为 $A_{i-1}$ 的值域，注意无穷大底数的单独处理和底数需要大于 $\max A_i$。

题解提供的做法是证明了合法底数的连续性和单调性然后用二分查找答案，实现起来应该略容易一些。

Ender_hz:

_istina_:

MeowScore: