← 返回题目列表

AtCoder · arc003_4

D. 随机更换座位

中文机器翻译题面 查看原题

問題文

在高桥先生工作的 Coder,我们总是 1 所有员工围坐在一张圆桌旁开会。
我们每个人都有自己喜欢的座位,所以我们总是坐在同一个座位上,但今天我们决定换座位。
高桥随机 2 选择人员并交换位置一定次数后的座位安排成为新的座位安排。
然而,对于 AtCoder 来说不幸的是,如果将他们放在一起,他们会在会议期间聊天并扰乱会议。 2 存在一群人。
高桥先生很认真,所以他会做这样的事情来确保会议顺利进行。 2 人类群体是 1 我也不希望这些组彼此相邻。
换座位后不要坐在一起。 2 一群人 1 求两对不相邻的概率。

入力

输入按以下格式给出。
N M K
A_{1} B_{1}
A_{2} B_{2}
: :
: :
A_{M} B_{M}
  • 1 行是一个整数,为员工总数 N (2 ≦ N ≦11),不得彼此相邻放置。 2 一个整数,表示人数对的数量 M (0 ≦ M ≦ 10),整数,表示交换次数 K (0 ≦ K ≦ 20) 用空格分隔。
  • 2 从行 M 行是 在1 行 1 请勿将配对彼此相邻放置。 2 人物之间用空格分隔。
  • i+1 行内整数 A_{i} 和整数 B_{i} (0 ≦ A_{i} < B_{i} < N) 不应彼此相邻放置。 2 代表一个人,每个数字代表高桥右边的人数。
  • 注意 A_i = 0 或B_i = 0 代表高桥本人。

出力

只是 K 交换时间后请勿将它们放在一起。 2 一群人 1 没有对彼此相邻的概率作为标准输出输出。 输出为 1 行。
误差至少是绝对误差和相对误差之一。 2e−3 如果低于则允许。
请在末尾输出换行符。

入力例 1

4 1 1
0 3

出力例 1

0.333333333333
  • 换座位之前,4 人员安排如下图。
  • 1 更换座位时,0 和 3 的 2 为了防止人们站在一起, 替换
    • 0 和 1 。
    • 2 和 3 。
  • 的 2 没错。4 来自人 2 如何选择某人 6 存在,所以满足条件的概率为 2/6 答案是 1/3 。

入力例 2

5 4 20
0 1
0 2
0 3
0 4

出力例 2

0
  • 高桥君以外的人 4 人中,有能站在高桥君身边的人。 1 由于没有人,因此条件永远不会满足。

入力例 3

5 1 2
0 3

出力例 3

0.52
  • 2 交换后, 如何交换0 和 3 以使它们彼此不相邻 52方法有很多。
  • 5 来自人 2 选择一个人 2 次后,所有组合都被 (_5C_2)^2 = 10^2 = 100 如下。
  • 因此,答案是 52÷100 = 0.52 。