Warning: session_start(): open(/tmp/sess_38c8ba10351104d7f19ada1f0bfb16a3, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 牛客多校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}