502001 - 酒店检查

【题目描述】酒店检查（detective）

侦探因为一个案件而检查酒店的N个房间。酒店的所有的房间都被紧锁，每个房间中随机锁了一把钥匙。例如当N＝3时，有6个可能的分布，每一个可能性是1 / 6。为方便起见，我们从将房间号从1编号到N，房间1号的钥匙编号为1，2号房间的钥匙编号为2…，要检查所有的房间，就必须用破坏一些门。但又不想破坏太多，所以策略为：在没有钥匙的时候，可以随机破坏一扇门，取出其中的钥匙，尝试用钥匙打开另外的门（然后取出钥匙去打开另外的门，直到不能打开任何的门的时候，接着破坏另外的门）。但要注意：不允许破坏1号房间的门而只能用钥匙打开，因为有一个非常重要的人住在1号房间。 侦探最多可以破坏k（k≤n）扇门，但是第一扇门只能用钥匙打开。求所有门能被打开（被破坏，或是被钥匙打开）的概率。

第一行是一个整数T (T≤200)，表示测试数据的个数。 以后每行包含两个整数N和k（1＜N≤20，1≤k＜N）。

每组测试数据输出一行，表示相应的可能性。小数点后的四位数字保存为四舍五入。

【样例解释】 当N＝3，有6种可能：

房间1	房间2	房间3	破坏次数

1 Key 1 Key 2 Key 3 不可能

2 Key 1 Key 3 Key 2 不可能

3 Key 2 Key 1 Key 3 2

4 Key 3 Key 2 Key 1 2

5 Key 2 Key 3 Key 1 1

6 Key 3 Key 1 Key 2 1

在前2个可能性中，因为钥匙1是锁定在1房间的本身，而侦探不能破坏房间1，所以不可能打开房间1。 在第3和第4个可能性中，侦探必须摧毁2和3的房间。在最后2个可能性中，侦探只需要摧毁一个房间。