| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.7 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 22 | 11 | 6 | 40.000% |
이번 MatKor Cup이 왜 FinAL인지 아는가? 이번 대회를 개최하기 전 동우는 이미 $0$회 대회부터 $6$회 대회까지 MatKor Cup을 총 $7$회 진행하며 $1$성구부터 $7$성구까지 모아, MatKor Cup을 없애달라는 소원을 빌었기 때문이다.
MatKor Cup이 없어지기 위해서는 $1$성구부터 $7$성구까지 공이 하나씩 필요하다. 지금 MatKor에는 $1$번부터 $7$번까지 총 $7$개의 공이 있고, 초기에는 모두 $1$성구이다. MatKor에는 부원은 $N$명이 있고, 각각의 부원은 만질 수 있는 공이 정해져 있다.
이제 하루에 한 번씩 다음 행위를 할 것이다. $N$명 중 $1$명의 부원을 동일한 확률로 골라 해당 부원이 만질 수 있는 공을 모두 한 번씩 만진다. $i$번 공을 만지면, $i$번 공의 별이 하나 추가되거나 없어진다. 단, $1$성구에서 별이 하나 없어지면 $7$성구가 되며, $7$성구에서 별이 하나 추가되면 $1$성구가 된다. 각 부원이 공을 만질 때 각각의 공의 별은 독립적으로 $\frac{1}{2}$의 확률로 추가되거나 없어진다.
오늘로부터 $P$일이 지나면 MatKor Cup 예비소집, $M$일이 지나면 MatKor Cup 본대회이다. 즉, 위의 행위를 $P$번 혹은 $M$번 하면 각각 예비소집과 본대회를 치르게 된다. 만약 이 시점에 공을 확인했을 때, $7$개의 공이 $1$성구부터 $7$성구까지 하나씩 존재하면 MatKor Cup은 없어진다. 단, 예비소집 때 이미 없어졌다면 본대회 때 다시 없어지지는 않는다.
그런데 그동안 MatKor Cup에 고통받은 사람들에게서 원기옥을 받은 동우는 한 가지 가능성을 더 만들었다. 공을 확인하는 시점에 $7$개의 공이 $1$성구부터 $7$성구까지 하나씩 존재하지 않더라도, $1,2,\cdots ,7$번 공이 각각 $x_1,x_2,\cdots ,x_7$성구일 경우에도 MatKor Cup이 없어진다.
MatKor Cup이 예비소집 날에 없어질 확률과 본대회 날에 없어질 확률을 구해보자.
첫 번째 줄에 부원의 수를 나타내는 정수 $N(1\le N\le 10^5)$, 예비소집과 본대회까지 남은 날의 수를 나타내는 정수 $P,M(1\le P<M\le 10^9)$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $N$줄에 걸쳐 $i$번째 줄에 $i$번째 부원이 만질 수 있는 공의 개수 $c_i(1\le c_i\le 7)$와 조작할 수 있는 공의 번호 $a_{i,1},a_{i,2},\cdots ,a_{i,c_i}(1\le a_1<a_2<\cdots <a_{c_i}\le 7)$가 한 줄에 공백으로 구분되어 주어진다.
$N+2$번째 줄에 동우가 추가로 만든 가능성을 의미하는 정수 $x_1,x_2,\cdots ,x_7(1\le x_i\le 7)$이 공백으로 구분되어 주어진다.
첫 번째 줄에 MatKor Cup이 예비소집 날에 없어질 확률을 $10^9+7$로 나눈 나머지를 출력한다.
두 번째 줄에 MatKor Cup이 예비소집 날에 없어지지 않고 본대회 날에 없어질 확률을 $10^9+7$로 나눈 나머지를 출력한다.
기약 분수 $\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 | 31 | $P=1$; $N,M\le 7$; $x=\left[ 1,2,3,4,5,6,7 \right]$ |
| 2 | 42 | $x=\left[ 1,2,3,4,5,6,7 \right]$ |
| 3 | 27 | 추가적인 제한 조건 없음 |
2 1 3 4 1 2 3 4 6 1 2 3 4 5 6 1 2 3 4 5 6 7
0 649200444
MatKor Cup이 예비소집 날에 없어질 수 있는 경우의 수는 없으므로 본대회 날에 없어질 확률만 따져보자.
먼저 $3$일 중 첫 번째 부원 $1$회, 두 번째 부원 $2$회 선정되어야 한다. 이 확률은 $\frac{3}{8}$이다.
$1,2,3,4$번째 공은 $3$번씩 변경되는데, 모두 최종 상태가 달라야 한다. 이 확률은 $\frac{27}{512}$이다.
$5,6$번째 공은 $2$번씩 변경되는데, $1$성구 상태로 돌아가지 않으면서 서로 다른 모양이 되어야 한다. 이 확률은 $\frac{1}{8}$이다.
MatKor Cup이 본대회 날에 없어질 확률은 위 확률을 모두 곱한 $\dfrac{81}{32\, 768}$이다.
1 1 111 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
0 502899806
2 3 4 4 1 2 3 4 6 1 2 3 4 5 6 2 3 1 5 6 7 4
649200444 187844993
1 11 111 7 1 2 3 4 5 6 7 1 1 1 1 1 1 1
595288894 293968025