문제 보기 - 비트 (kriii4_Q)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
2000 ms 512 MiB 9 4 44.44%

시간이 많은 그는 N개의 비트(0 또는 1을 가질 수 있는 변수)를 조작하는 일을 반복하고 있다. 지금까지 하던 것이 식상해진 그는 새로운 규칙으로 N개의 비트를 조작하려고 한다. 한 번의 조작이란 다음과 같은 작업을 의미한다.

  1. 비트 중에서 0인 것들을 먼저, 1인 것들을 나중에 놓는 방식으로 일렬로 늘어 놓는다. 즉 오름차순(엄밀히 비내림차순) 정렬한다.
  2. 그 다음 1 이상 N 이하의 정수 K개(K는 홀수)를 무작위로 뽑는다. 각 정수를 뽑을 확률은 모두 독립적으로, 같은 정수가 두 번 이상 뽑힐 수도 있으며, 1부터 N까지의 각 자연수가 뽑힐 확률은 모두 동일하다.
  3. 뽑힌 K개의 정수 각각에 대해서 정수가 i라면 i번째 비트를 토글한다. 즉, 0이면 1로, 1이면 0으로 바꾼다.

예를 들어, 그가 가진 비트가 0,1,0이고 K = 3이라고 해보자.

  1. 먼저 비트를 정렬하여 0,0,1로 만든다.
  2. K = 3개의 정수를 뽑아 1,3,1순서대로 뽑혔다고 해보자.
  3. 첫 번째 정수 1에 의해서 비트는 1,0,1이 된다. 두 번째 정수 3에 의해서 비트는 1,0,0이 된다. 세 번째 정수 1에 의해서 비트는 0,0,0이 된다.

위의 과정에서 알 수 있듯, 사실 비트의 순서가 어떻게 되어있는지는 크게 중요한 것이 아니고 개수가 중요하다. 그는 조작을 한 후에 모든 비트가 1이 되면 조작을 끝내고 자러 갈 것이다. 현재 비트 중에서 0인 것의 개수가 z개일 때 모든 비트를 1로 만들기 위한 조작 횟수의 기댓값을 구하는 프로그램을 작성하라.


입력

첫 번째 줄에는 비트의 개수와 뽑게 되는 정수의 개수를 의미하는 두 자연수 N, K가 공백으로 구분되어 주어진다. K는 홀수이다.


부분문제

부분문제
점수
N
K
1
9
1 ≤ N ≤ 100
K = 1
2
91
1 ≤ N ≤ 100
0 ≤ K ≤ 109


출력

N개의 줄에 걸쳐 답을 출력한다. z번째 줄에는 현재 비트 중에서 0인 것의 개수가 z개일 때 모든 비트를 1로 만들기 위해 필요한 조작 횟수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. b-1b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 답이 존재하는 것이 확인된 입력만 들어온다.


입출력 예제

입력 예제 출력 예제
1 11
2 13
4
5 99812420891
724220653
692773316
452277443
513756160