kjk9704   1년 전

원활한 해석을 위해 의역 및 추가도 있는 점 양해 부탁드립니다.

[문제]

방금 친구와 함께 프로그래밍 대회에 참가했습니다. 

안타깝게도 대회에 나온 모든 문제를 All Kill 할 수는 없었지만, 이제 모든 문제를 All Kill 할 수 있는 전략이 있는지 궁금합니다.

(여기서 All Kill은 모든 문제를 해결한 상태를 의미합니다.)

문제를 해결하는 데는 아이디어 구상 단계와 프로그램 코딩 단계 이렇게 두 단계가 있습니다. 

친구는 모든 아이디어 구상을 담당하고, 당신은 모든 프로그램 코딩을 담당합니다.

각 문제에 대해 코딩하는 데 걸리는 시간을 정확히 계산했습니다.

하지만 대회에서 문제를 해결하려면 친구가 먼저 아이디어를 얻어야 합니다.

친구가 해결책 아이디어를 얻는 시간을 추정하는 방법을 잘 모르기 때문에 이렇게 설계합니다.

- 모든 문제에 대해 친구는 대회 진행 중 균일하게 무작위 순간에 이 문제를 푸는 방법에 대한 아이디어를 얻습니다. 

- 이 모든 문제는 독립적인 무작위 변수입니다. 

- 한 번에 하나의 문제만 코딩할 수 있으므로 언제든지 여러 문제가 줄을 설 수 있습니다. 

- 항상 가장 낮은 숫자의 문제를 먼저 코딩하는 것이 우선입니다

이 작업을 분 단위로 수행하므로 숫자가 높은 문제를 코딩하기 전에 친구가 아이디어를 얻으면 숫자가 낮은 문제를 코딩하는 것으로 전환하지만, 이 작업은 하지 않는 것이 좋습니다. 대회 전략 전환은 인간의 뇌에서도 비용이 많이 드는 작업입니다!


대회 전략은 매 분마다 다음과 같이 설계할 수 있습니다 :

- 아직 아이디어가 없는 각 문제에 대해 친구는 확률 1/(경기 종료까지 남은 시간)로 문제를 풀 수 있는 아이디어를 얻게 됩니다. 

- 친구는 같은 시간에 여러 문제를 풀 수 있는 아이디어를 얻을 수 있습니다.

- 여전히 코드 시간이 필요하고 친구가 해결책 아이디어를 얻은 문제 중에서 가장 낮은 숫자의 문제를 선택하고 다음 1분 동안 코드화하는 데 사용합니다(문제가 조건을 충족하지 않으면 이 단계에서는 아무것도 하지 않습니다).

이 두 사건이 함께 발생할 확률을 알고 싶습니다 :

- 당신의 팀은 대회가 끝날 때까지 모든 문제를 코딩하는 것을 마칩니다

- 각 문제에 대해 해당 문제를 코딩하는 데 소요되는 시간은 연속적인 간격입니다

p를 확률, n을 대회에 나온 문제 수, t를 대회에서 주어진 제한 시간이라고 합시다. 

p · t^n이 정수임을 알 수 있습니다. 

(p · t^n) (mod 998,244,353)의 값을 출력합니다. 

998,244,353은 큰 소수입니다.

[문제 요약]

문제 개수가 n, 대회에 주어진 시간은 t입니다.

문제 푸는 방법은 다음과 같습니다.(반드시 이 순서를 지켜야 합니다.)

1. 아이디어 생각한다

2. 코딩한다

각 문제 별로 코딩 시간은 다르며 각 문제에 대해 아이디어를 얻을 확률은 1/(경기 종료까지 남은 시간)입니다.

풀이가 떠오르면 바로 코딩을 시작하는데, 항상 풀이가 떠오른 문제들 중에서 번호가 가장 낮은 문제부터 풀어야 합니다. 

즉, 5번 문제를 코딩 중인데 1번 문제의 풀이가 떠올랐다면 1번 문제의 코딩을 바로 시작해야 합니다. 

반대로 3번 문제을 코딩하는 도중에 6, 9번 문제의 풀이가 떠올랐으면 3번 문제의 코딩을 끝내고 6, 9번을 순서대로 코딩합니다.

이와 같이 문제를 푼다고 했을 때, All Kill할 확률을 p라고 합니다.

각 문제의 코딩 시간 x_i가 차례대로 주어질 때

All Kill할 확률 p를 구하고 (p * t^n) % 998,244,353을 출력하면 됩니다.

(단, 모든 코딩 시간의 합은 대회에서 주어진 제한 시간 t보다 작거나 같음을 보장 받습니다.)

[입력]

첫 번째 입력 줄에는 두 개의 공간으로 구분된 정수 n(1 ≤ n ≤ 105)과 t(1 ≤ t ≤ 108)가 포함되어 있으며, 대회에서 n개의 문제가 발생했으며 대회는 t분 동안 지속되었습니다.
다음 n개의 각 줄에는 단일 정수 x(1 ≤ x ≤ 103)가 포함되어 있습니다. 이는 각 문제를 분 단위로 코딩하는 시간입니다. 이 시간의 합은 t보다 작거나 같음이 보장됩니다.

[출력]

단일 정수를 출력합니다. 

여기서 p는 위에서 언급한 두 사건이 함께 일어날 확률을 의미합니다. 

(p · t^n) (mod 998,244,353)를 출력하시면 됩니다.

댓글을 작성하려면 로그인해야 합니다.