생일 파티

시간 제한5초메모리 제한256 MB

요약

N명의 손님이 각각 다른 무작위 손님에게 선물을 주며 k명이 방향성 선물 순환을 이룰 확률을 구합니다.

난이도: 어려움10점 중 8점
유형: 조합론, 확률, 수학
정답자: 아직 제출이 없습니다

문제

생일 파티에 $N$ 명이 초대받았다. 모두 선물을 하나씩 가져오고, 그 선물을 누구에게 줄지는 무작위로 정한다. 자기 자신에게는 줄 수 없고, 나머지 $N-1$ 명이 뽑힐 확률은 모두 같다. 사람마다 고르는 것은 서로 독립이므로 선물을 여러 개 받는 사람도 있고 하나도 받지 못하는 사람도 있다.

서로 다른 $k$ 명 $p_1, p_2, \dots, p_k$ 가 있어서 $p_1$ 이 $p_2$ 에게, $p_2$ 가 $p_3$ 에게 선물을 주고, 같은 식으로 이어져 $p_k$ 가 다시 $p_1$ 에게 선물을 주는 경우를 선물 고리라고 하자. 길이가 $k$ 인 선물 고리가 하나라도 생길 확률을 구하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에는 각각 두 정수 $N$ 과 $k$ 가 공백으로 구분되어 주어진다.

$0 < T \le 30$
$2 \le N \le 10^7$
$2 \le k \le N$

출력

각 테스트 케이스마다 구한 확률을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 하나씩 출력한다. 확률이 $1$ 이면 1.000000을, $0.313469843\ldots$ 이면 0.313470을 출력한다.

예제1

예제 1

입력

예상 출력