| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 39 | 25 | 18 | 64.286% |
이번 MatKor Cup에는 총 $N$명의 참가자가 참가하였으며, 대회장에는 $M$개의 자리가 준비되어 있다. 종우는 $N$명의 참가자들에게 각각 서로 다른 자리를 한 개씩 미리 배정해 두었고, 동우가 종우에게 어떻게 자리를 배정했는지 물어보았다.
종우는 그냥 알려줄 수는 없고, 동우에게 $N$명의 자리를 예측해 보라고 했다. 동우는 $M$개의 자리 중 서로 다른 $N$개의 자리를 고른 후, 각 참가자의 자리를 예측했다.
동우가 예측한 $N$명 중, 종우가 배정한 자리와 같은 자리에 앉은 사람 수가 $i$명일 확률을 각각 구해보자.
종우와 동우는 가능한 모든 경우에 대해 동일한 확률로 자리를 배정하거나 예측한다.
첫 번째 줄에 참가 인원과 자리의 개수 $N,M(1\le N\le M\le 5,000円,000円)$이 공백으로 구분되어 주어진다.
첫 번째 줄에 동우가 예측한 $N$명 중, 종우가 배정한 자리와 같은 자리에 앉은 사람 수가 $i(0\le i \le N)$명일 확률을 10ドル^9+7$로 나눈 나머지를 한 줄에 출력한다. 이때, 0ドル$부터 $N$까지 총 $N+1$개의 수를 공백으로 구분하여 출력해야 함에 유의하자.
기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.
주어진 조건 내에서 확률이 정수 혹은 분모가 10ドル^9+7$의 배수가 아닌 유리수로 나타내어짐을 증명할 수 있다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 26 | $N,M\le 5,000円$ |
| 2 | 74 | 추가적인 제한 조건 없음 |
1 1
0 1
한 명이 참가하고, 자리가 한 개일 때는 반드시 1ドル$명의 자리를 맞추므로 0ドル$의 확률로 0ドル$명을 맞추고, 1ドル$의 확률로 1ドル$명을 맞춘다.
1 2
500000004 500000004
한 명이 참가하고, 자리가 두 개일 때는 $\frac{1}{2}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{1}{2}$의 확률로 1ドル$명의 자리를 맞춘다.
2 2
500000004 0 500000004
참가자 두 명을 $A,ドル $B$라고 하면 종우는 $AB$혹은 $BA$로 자리를 배치했으며, 동우는 $AB$와 $BA$ 중 하나로 예측할 것이다. 즉, 총 2ドル\times 2=4$가지의 경우의 수 중 $\frac{2}{4}$의 확률로 0ドル$명의 자리를 맞추고, 0ドル$의 확률로 1ドル$명의 자리를 맞추며, $\frac{2}{4}$의 확률로 2ドル$명의 자리를 맞춘다.
2 3
500000004 333333336 166666668
총 6ドル\times 6=36$가지의 경우의 수 중 동우가 $\frac{18}{36}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{12}{36}$의 확률로 1ドル$명의 자리를 맞추고, $\frac{6}{36}$의 확률로 2ドル$명의 자리를 맞춘다.
2 4
583333338 333333336 83333334
총 12ドル\times 12=144$가지의 경우의 수 중 동우가 $\frac{84}{144}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{48}{144}$의 확률로 1ドル$명의 자리를 맞추고, $\frac{12}{144}$의 확률로 2ドル$명의 자리를 맞춘다.
3 5000000
291171085 327315168 186142224 195371531
University > 고려대학교 > MatKor Cup > 제5회 고려대학교 MatKor Cup: 2024 Summer/Fall H번