問題文
我们每个人都有自己喜欢的座位,所以我们总是坐在同一个座位上,但今天我们决定换座位。
高桥随机 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 代表高桥本人。
出力
误差至少是绝对误差和相对误差之一。 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 。