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)$。

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

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

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

Ender_hz:

_istina_:

MeowScore: