AT_abc483_g [ABC483G] Qualification 题解

BennyT · 2026-11-08 19:18:45 · 题解

AT_abc483_g [ABC483G] Qualification 题解

依旧计数转期望，期望转计数

思路

首先显然可以把 P 固定为 1,2,\dots,n，最后再给答案乘 n!，这样是对答案没有影响的，这样就只用考虑 Q 是排列的情况。

设 A,B,C,D 分别表示：

设 A 中有 m 个人，则 B,C 中各有 k-m 个人，D 中有 n-2k+m 个人。

考虑两种方法分别会选哪些人。

方法 1：先选 P 的前 k 个再选 Q 的前 k 个

先选 P 的前 k 个即为 A \cup B，则再剩下的 C,D 中选 k 个一定会选 C 的全部元素，剩下的 m 个从 D 中选。

方法 2：先选 Q 的前 k 个再选 P 的前 k 个

同理，先选 Q 的前 k 个即为 A \cup C，则再剩下的 B,D 中选 k 个一定会选 B 的全部元素，剩下的 m 个从 D 中选。

那么我们会发现，A,B,C 无论如何都一定会被选上，所以只有 D 中的元素能对 f(P,Q) 产生贡献。

设 t=n-2k，则 D 的大小即为 t+m。

设 D_Q 表示通过方法 1 选出来的在 D 中 Q 排名最靠前的 m 个，D_P 表示通过方法 2 选出来的在 D 中 P 排名最靠前的 m 个。

固定 m，则 D 可以视为一个长度为 t+m 的随机排列，则我们要求的即为 |D_Q\ \backslash\ D_P| 的期望值，后文表示为 \mathbb{E}[|D_Q\ \backslash\ D_P|]。

设在 D 中，D_Q 是固定的 m 个数，由于 |D|=t+m，则一个在 D_Q 中的数同时在 D_P 中的概率为 \frac{m}{t+m}，则 \mathbb{E}[|D_Q\cap D_P|]=m\times\frac{m}{t+m}=\frac{m^2}{t+m}，易得 \mathbb{E}[|D_Q\ \backslash\ D_P|]=m-\mathbb{E}[|D_Q\cap D_P|]=m-\frac{m^2}{t+m}=\frac{tm}{t+m}。

然后我们需要计算有多少个 Q 满足前 k 个数有 m 个 \le k 的数。设此数为 cnt_m，首先需要从 1 \sim k 中选择 m 个数放到 1 \sim k 的位置，方案数为 \binom{k}{m}，再从剩下的 n-k 个 >k 的数中选 k-m 个放在 1 \sim k 的位置，方案数为 \binom{n-k}{k-m}，然后两边随便放，方案数为 k!(n-k)!，整理得 cnt_m=\binom{k}{m}\binom{n-k}{k-m}k!(n-k)!。

则最终答案即为：

预处理逆元阶乘可以做到 O(\sum n)。

代码不贴了，太好写了。