Snuke는 임의의 수 생성기를 발견했다. 이 생성기는 1과 N 사이의 정수(양 끝 포함)를 생성한다. 정수 수열 A1, A2, …, AN은 각 정수가 생성될 확률을 나타낸다. 정수 i (1 ≤ i ≤ N)는 확률 Ai/S로 생성되며, 여기서 S = ∑_{i=1}^{N} Ai이다. 정수를 생성하는 과정은 생성기가 실행될 때마다 독립적으로 수행된다. Snuke에게는 현재 값이 0인 정수 X가 있다. 그는 다음 연산을 원하는 만큼 반복할 수 있다.
생성기로 정수 v를 생성하고 X를 X + v modM로 바꾼다.
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으로 나눈 나머지를 출력하시오.
nnaxh0 1년 전
문제
Snuke는 임의의 수 생성기를 발견했다. 이 생성기는 1과 N 사이의 정수(양 끝 포함)를 생성한다. 정수 수열 A1, A2, …, AN은 각 정수가 생성될 확률을 나타낸다. 정수 i (1 ≤ i ≤ N)는 확률 Ai/S로 생성되며, 여기서 S = ∑_{i=1}^{N} Ai이다. 정수를 생성하는 과정은 생성기가 실행될 때마다 독립적으로 수행된다. Snuke에게는 현재 값이 0인 정수 X가 있다. 그는 다음 연산을 원하는 만큼 반복할 수 있다.
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으로 나눈 나머지를 출력하시오.
제한