nnaxh0   1년 전

문제

Snuke는 임의의 수 생성기를 발견했다. 이 생성기는 1과 N 사이의 정수(양 끝 포함)를 생성한다. 정수 수열 A1, A2, …, AN은 각 정수가 생성될 확률을 나타낸다. 정수 i (1 ≤ i ≤ N)는 확률 Ai/S로 생성되며, 여기서 S = ∑_{i=1}^{N} Ai이다. 정수를 생성하는 과정은 생성기가 실행될 때마다 독립적으로 수행된다. Snuke에게는 현재 값이 0인 정수 X가 있다. 그는 다음 연산을 원하는 만큼 반복할 수 있다.

  • 생성기로 정수 v를 생성하고 X를 X + v mod M로 바꾼다.

X가 K가 될 때까지 필요한 연산의 기대값을 구하고, 998244353으로 나눈 나머지를 출력해라. 더 정확히 말하면, 기대값을 기약분수 P/Q로 나타냈을 때, 0 ≤ R < 998244353인 유일한 정수 R이 존재하여 R × Q ≡ P mod 998244353 이 성립할때, 이 R을 출력한다.

X가 K가 될 때까지의 기대 연산 횟수는 유한한 유리수임이 증명 가능하다. 다만, 이 값의 998244353 모듈러 정수 표현이 항상 정의될 수 있음은 증명되지 않았다. 그러나 0으로 나누는 문제는 발생하지 않는다. 더 정확히 말하면, 이 문제를 흡수 마르코프 체인(absorbing Markov chain)으로 모델링할 수 있으며, 모든 테스트에서 기본 행렬(fundamental matrix)을 998244353 모듈러로 정의할 수 있음을 보장한다.

입력

표준 입력으로 다음 형식으로 주어진다.

N M K

A1 A2 … AN

출력

X가 K가 될 때까지 필요한 연산의 기대값을 998244353으로 나눈 나머지를 출력하시오.

제한

  • 1 ≤ N ≤ min(500, M-1)
  • 2 ≤ M ≤ 1018
  • 1 ≤ K ≤ M-1
  • 1 ≤ Ai ≤ 100
  • 입력의 모든 값은 정수이다.

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