冒泡排序

题目描述

给出以下定义


算法 1 冒泡排序


输入:一个⻓度为 n 的排列 P。


输出: 排序后的结果。


小 S 开始专注于研究⻓度为 $n$ 的排列,他想知道,在你运气足够好的情况下(即每次冒泡排序的交换次数都是可能的最少交换次数,仿佛有上帝之手在操控),对于一个等概率随机的⻓度为 $n$ 的排列,进行这样的冒泡排序的期望交换次数是多少?

思路

令 $f_i$ 表示排列有 $i$ 个数时的期望交换次数。

我们考虑一个排列 $p$,设它的第 $n$ 位为 $k$,第 $k$ 位为 $x$。现在我们将 $x$ 看作 $n$,对前 $n-1$ 个数进行上述排序,期望操作次数为 $f_{n-1}$。如果 $k\neq n$,那么我们再交换 $n, k$,排序结束;如果 $k=n$,此时的 $p$ 已经有序。$k$ 的值共有 $n$ 种情况,其中 $n-1$ 种情况需要再交换一次,得出:

$$f_i=f_{i-1}+\dfrac{i-1}{i}$$

预处理逆元后,$\Theta (n)$预处理出所有可能的答案,$\Theta (1)$ 回答每个询问。

然后我们考虑怎么预处理逆元。

首先,已知 $1^{-1} \equiv 1 \pmod p$。

我们设 $p = k\cdot i + r,~r < i,~1 < i < p$.

在模意义下就是 $k\cdot i + r \equiv 0 \pmod p$。

两边同时乘上 $i^{-1}\cdot r^{-1}$,得到:

就可以线性处理逆元了。

代码

情报中心

题目描述

最近,C 国成功地渗透进入了 D 国的一个城市。这个城市可以抽象成一张有 n 个节点,节点之间有 m 条双向道路连接的无向图,每条道路的⻓度都为 1 。

经过侦查,C 国情报部部⻓ GGB 惊讶地发现,这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这个城市内设立情报机构。情报专家 TAC 在侦查后,安排了 $q$ 种设立情报机构的方案。这些方案中,第 $i$ 种方案将计划建立 $k_i$ 个情报机构,第 $j$ 个情报机构可以安排人员到距离其不超过 $d_{i,j}$ 的节点上收集情报。

但是,由于人手不足,GGB 只能安排上述 $q$ 种方案中的一种进行实施。为了评估一种方案的性能,我们把能够收集到情报的节点数量视为这种情报的价值。现在,你被 GGB 和 TAC 派来侦查,请你统计每一种方案的价值。

思路

代码

百鸽笼

题目描述

原题矫揉造作,优化题面如下:

给定一个数列,有三种操作:

  1. 删去左端点;
  2. 左端点前插入一个数 $v$;
  3. 询问从左到右数,$[l, r]$ 中第 $k$ 大的数字。

思路

将数列翻转,用主席树维护每个数字的前缀出现次数,每次修改新增一个版本。

本题空间限制为 $\text{262144 KB}$,数组要精简,离散化不要使用 $map$。

代码