레이팅 미적용*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
베시는 유명한 온라인 게임을 재미있게 즐기고 있다. 이 게임에는 서로 다른 라벨과 크기를 가진 세포들이 여럿 있고, 승자 하나만 남을 때까지 세포들이 다른 세포를 잡아먹는다.
한 줄에 왼쪽부터 오른쪽으로 \(1\dots N\)의 라벨이 붙은 \(N\) (\(2\le N\le 5000\))개의 세포가 있고, 초기 크기는 \(s_1,s_2,\dots,s_N\) (\(1\le s_i\le 10^5\))이다. 세포가 두 개 이상 남아 있는 동안, 인접한 세포 쌍 하나가 균등한 확률로 무작위로 선택되어 다음 규칙에 따라 하나의 새 세포로 합쳐진다.
라벨이 \(a\)이고 현재 크기가 \(c_a\)인 세포와 라벨이 \(b\)이고 현재 크기가 \(c_b\)인 세포가 합쳐지면, 합쳐진 세포의 크기는 \(c_a+c_b\)이고 라벨은 더 큰 세포의 라벨이 되며, 크기가 같으면 더 큰 라벨을 따른다. 형식적으로, 합쳐진 세포의 라벨은 \(\begin{cases} a & c_a > c_b \\ b & c_a < c_b \\ \max(a,b) & c_a = c_b \end{cases}\)이다.
\(1\dots N\) 범위의 각 라벨 \(i\)에 대해, 최종 세포의 라벨이 \(i\)일 확률은 \(b_i\not\equiv 0\pmod{10^9+7}\)인 \(\frac{a_i}{b_i}\) 꼴로 나타낼 수 있다. \(a_ib_i^{-1}\pmod{10^9+7}\)을 출력하여라.
출제: Benjamin Qi
배점
- 입력 3: \(N\le 8\)
- 입력 4-8: \(N\le 100\)
- 입력 9-14: \(N\le 500\)
- 입력 15-22: 추가 제약 없음.
출제: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(s_1,s_2,\dots, s_N\)이 주어진다.
\(1\dots N\)의 각 \(i\)에 대해, 최종 세포의 라벨이 \(i\)일 확률을 \(10^9+7\)로 나눈 나머지로 각각 별도의 줄에 출력한다.
3
1 1 10
500000004
500000004There are two possibilities, where \((a,b)\to c\) means that the cells with labels
\(a\) and \(b\) merge into a new cell with label \(c\).
(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3
So with probability \(1/2\) the final cell has label 2 or 3.
4
3 1 1 1666666672
0
166666668
166666668The six possibilities are as follows:
(1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1
(1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1
(2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1
(2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3
(3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4
(3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1
So with probability \(2/3\) the final cell has label 1, and with probability \(1/6\)
the final cell has label 3 or 4.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Platinum