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: 给定一个类线段树的数据结构，根节点对应区间 $[1, n]$。对于区间为 $[l, r]$ 的节点：

• 若 $2|(r-l+1)$，则两个子节点对应区间分别为 $\left[l, \dfrac{l+r-1}{2}\right], \left[\dfrac{l+r+1}{2}, r\right]$；
• 若 $2\not\mid (r-l+1)$，则两个子节点有 $\dfrac{1}{2}$ 的概率对应 $\left[l, \dfrac{l+r}{2}-1\right], \left[\dfrac{l+r}{2}, r\right]$，有 $\dfrac{1}{2}$ 的概率对应 $\left[l, \dfrac{l+r}{2}\right], \left[\dfrac{l+r}{2}+1, r\right]$。

在树上查询区间 $[x, y]$ 时，从根节点开始。在某节点时：

• 若该节点对应区间是 $[x, y]$ 的子集，则结束；
• 否则，若该节点左（右）子节点对应区间与 $[x, y]$ 的交集不为空，则访问左（右）节点；
• 最终返回访问的节点数。

记 $query(x, y)$ 为在树上查询区间 $[x, y]$ 的结果，求满足 $query(x, y)=i, \forall 1\le i\le 2n$ 的区间期望数量。

思路如下：不难证明在对应区间 $[l, r]$ 的节点查询子区间 $[x, y]$ 的结果的分布仅与区间长度 $r-l+1$ 有关。

对于区间长度 $len$，我们维护 $dp_{len,k}$ 为查询结果恰为 $k$ 的子区间期望数量，同时维护 $pre_{len, k}$ 为查询结果恰为 $k$ 的前缀区间期望数量，$suf_{len, k}$ 为查询结果恰为 $k$ 的后缀区间期望数量，那么我们有:

边界条件：

• $dp_{1,1}=pre_{1,1}=suf_{1,1}=1$。

转移方程：

• 对于 $dp$:
  • 若访问的子区间恰为自身，则 $dp_{len, 1}=1$；
  • 若访问的子区间恰在某个儿子内，则对 $dp_{len, k},k\ge 2$ 的贡献为 $dp_{len^L, k-1}+dp_{len^R, k-1}$；
  • 若访问的子区间跨越两个儿子且不为自身，则对 $dp_{len, k},k\ge 3$ 的贡献为 $\sum\limits_{\quad i,j\ge 1,i+j=k-1} suf_{len^L, i}\cdot pre_{len^R, j}$。

• 对于 $pre$（$suf$ 同理）:
  • 若访问的子区间恰为自身，则 $pre_{len, 1}=1$；
  • 若访问的子区间恰在左儿子内，则对 $pre_{len, k}, k\ge 2$ 的贡献为 $pre_{len^L, k - 1}$；
  • 若访问的子区间跨越两个儿子且不为自身，则对 $pre_{len, k}, k\ge 3$ 的贡献为 $pre_{len^R, k - 2}$。

特别地，当 $2\not\mid len$ 时需要将两种 $(len^L,len^R)$ 的情况取平均。

Ender_hz: 题意为 $m$ 进制下，给定 $n$ 个互不相同的数码 $0\le a_i < m,1\le i\le n$，恰组成两个数 $x,y$，求 $\min |x-y|$。

不妨设 $x<y$，$a$ 递增。记 $x=\overline{x_{k-1}\cdots x_1x_0}, y=\overline{y_{k-1}\cdots y_1y_0}$（高位可补 $0$），此时 $y-x=\sum\limits_{i=0}^{k-1}(y_{i}-x_{i})m^i$。

1. $2|n$

显然要使 $y-x$ 尽量小，就有 $k=\dfrac{n}{2}$，$y_{k-1}>x_{k-1}$ 但 $y_{k-1}-x_{k-1}$ 尽量小（$\iff$ 两者在 $a$ 中相邻），且 $y_{k-2}<y_{k-3}<\cdots<y_1<y_0<x_0<x_1<\cdots<x_{k-3}<x_{k-2}$。容易证明，当且仅当 $y_{k-2}<\cdots<y_0<x_{k-1}<y_{k-1}<x_0<\cdots<x_{k-2}$ 时，$\sum\limits_{i=0}^{k-2}(y_{i}-x_{i})m^i$ 最小，且 $x_{k-1}, y_{k-1}$ 单向移动时，前式一定单调增，因此只需找到两侧距离 $a_k,a_{k+1}$ 最近的 $a_p,a_{p+1}$ 满足 $a_{p+1}-a_p=\min\limits_{1\le i<n} a_{i+1}-a_{i}$ 作为 $x_{k-1},y_{k-1}$ 后选择两者中的最小值即为所求。

2. $2\not\mid n$

显然要使 $y-x$ 尽量小，就有 $k=\dfrac{n+1}{2}$，此时有 $x_{k-1}=0$，。

(1) $a_1 = 0$

若 $y_{k-1}=a_1=0$，则可转化为剩余 $a_{2..n}$ 的 $n-1$ 个数的问题，通过第 1 种情况解决；

若 $y_{k-1}\neq a_1$，不难证明要使 $y-x$ 最小，一定有 $y_{k-1}=a_2$，剩余部分与确定了高位的第 1 种情况同理。

(2) $a_1 \neq 0$

不难证明要使 $y-x$ 最小，一定有 $y_{k-1}=a_1$，剩余部分与确定了高位的第 1 种情况同理。

Ender_hz:

_istina_:

MeowScore: