自动搬运

查看原文

来自洛谷，原作者为

	moyu_028 **

搬运于2025-08-24 22:22:38，当前版本为作者最后更新于2020-06-27 12:12:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解。

• 对于测试点 1

什么都不输出即可得到 $10$ 分。

• 对于测试点 2

我们可以直接枚举箭头的方向，然后直接找字典序第 $k$ 小的拓扑序，时间复杂度 $O(2^mn)$。

• 对于测试点 3

结论：字典序第 $k$ 小的拓扑序为 $n$ 的全排列中字典序第 $k$ 小的那个序列。

证明：考虑先证明当 $k = 1$ 时答案的字典序为 $1$ ~ $n$。连边的方式为从编号小的点连向编号大的点。

为什么这样是最优的？

考虑对于 1 号点，它在一开始时就没有入边，因为如果存在一个点 $x$，有一条从 $x$ 到 1 的有向边的话，那么 $x < 1$，显然 $x$ 不存在。

那么对于 2 号点，如果存在一个点 $x$，有一条从 $x$ 到 2 的有向边的话，那么 $x < 2$，显然 $x$ 不存在，因为 1 号点和它所连出去的边都消失了。

那么对于 $i$ 号点，如果存在一个点 $x$，有一条从 $x$ 到 $i$ 的有向边的话，那么 $x < i(i > 1)$，显然 $x$ 不存在，因为 $1$ ~ $(i - 1)$ 号点和它所连出去的边都消失了。

因此可以证明当 $k = 1$ 时答案的字典序为 $1$ ~ $n$。

考虑证明我们在上面所提到的结论：字典序第 $k$ 小的拓扑序为 $n$ 的全排列中字典序第 $k$ 小的那个序列。

我们不妨换一种方式来证明它，我们考虑证明：对于 $n$ 的全排列中的任意一个排列 $p_1$ ~ $p_n$，它都是可能的拓扑序。

• 证明：连边方式，将原图中的 $p_i$ 号点的编号换成 $i$ 后，从编号小的点向编号大的点连一条有向边。接下来的证明同上所述。

因此对于 $k = 1$ 的测试数据，我们直接从编号小的点向编号大的点连一条有向边即可。

• 对于测试点 4

利用上面的结论，暴力求出答案的排列然后有上面所说的结论连边即可。

其实这道题一开始的数据范围是 $1 \leq n \leq 10^5,1 \leq m \leq 2 \times 10^5,1 \leq k \leq 10^{5000}$，但是后来被削弱了，因为如果加强到这个数据范围的话后面的一部分就是套路题了（这里的套路指的是快速求出 $n$ 的全排列中字典序第 $k$ 小的那个排列），于是这套比赛又多了一道水题。