====== 牛客多校6 ====== ^ 比赛时间 ^ 比赛名称 ^ 赛中过题 ^ 总计过题 ^ 题目总数 ^ 罚时 ^ Dirt ^ 校内排名 ^ | 25.07.31 | [[20250731|牛客多校6]] | 4 | 10 | 13 | 552 | 2/6 | 12/19 | ===== 赛时 ===== ==== C 00:32 +0 ==== 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 ix_{k-1}$ 但 $y_{k-1}-x_{k-1}$ 尽量小($\iff$ 两者在 $a$ 中相邻),且 $y_{k-2}