页面无法加载？点击这里可能会修复。
Placeholder

#6223
子任务

셀 병합 2s 1024MB

问题

정올이는 유명한 온라인 게임을 하고 있습니다. 게임에서는 여러 개의 셀들이 서로 격돌하여 하나의 최종 셀만 남게 됩니다. 각 셀은 다른 셀에 의해 먹히면서 합쳐집니다. 이 과정에서 최종적으로 승리할 셀의 레이블을 구하는 문제입니다.

게임의 규칙은 다음과 같습니다:

  • 셀들은 N개가 주어지며, 각 셀은 1번부터 N번까지 레이블을 가지고 있고, 크기는 s_1, s_2, \dots, s_N로 주어집니다.

  • 셀들이 합쳐지는 규칙은 다음과 같습니다. 두 개의 인접한 셀을 임의로 선택하여 하나의 셀로 합칩니다. 두 셀이 합쳐질 때, 각 셀의 레이블과 크기를 비교하여 새로운 셀의 레이블과 크기를 결정합니다:

    • 레이블이 작은 셀과 큰 셀이 합쳐지면, 결과 셀의 레이블은 큰 셀의 레이블로 결정됩니다.

    • 만약 크기가 같다면, 레이블이 더 큰 셀이 새로운 셀의 레이블이 됩니다.

각 레이블에 대해 최종적으로 그 레이블을 가진 셀이 남을 확률을 구해야 합니다.

확률은 \frac{a_i}{b_i} 형태로 주어집니다. 여기서 b_i는 10^9+7로 나눈 나머지가 0이 아닌 값입니다. 그러므로 각 확률을 a_i \times b_i^{-1} \mod (10^9+7) 형태로 출력해야 합니다.


输入

첫 번째 줄에 N이 주어집니다.

두 번째 줄에 셀들의 크기 s_1, s_2, \dots, s_N​이 주어집니다.


输出

각 레이블 1부터 N까지, 최종적으로 해당 레이블을 가진 셀의 확률을 출력합니다. 확률은 10^9+7로 나눈 나머지 값으로 출력합니다.


子任务

编号 分数 条件
#125分

N \le 8

#225分

N \le 100

#325分

N \le 500

#425分

추가 제약 조건 없음


示例 #1

3
1 1 1
0
500000004
500000004

주어진 예제에서 가능한 두 가지 경우는 다음과 같습니다:

  1. (1, 2) -> 2, (2, 3) -> 2

  2. (2, 3) -> 3, (1, 3) -> 3

따라서, 최종적으로 셀의 레이블이 2번이나 3번이 될 확률은 각각 \frac{1}{2}​입니다.


示例 #2

4
3 1 1 1
666666672
0
166666668
166666668

가능한 6가지 경우는 다음과 같습니다:

  1. (1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1

  2. (1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1

  3. (2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1

  4. (2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3

  5. (3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4

  6. (3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1

따라서, 셀의 레이블이 1번이 될 확률은 \frac{2}{3}​, 3번 또는 4번이 될 확률은 각각 \frac{1}{6}​입니다.



来源

USACO 2024 January Platinum

需要登录才能编写代码。