간단한 확률 문제

풀이는 다음과 같다.

• 색이 $x$인 공의 수를 $p_x$라 하자. 이때 최종 공의 색이 $x$일 확률은 $\frac{p_x}{n}$이다.
• $m$의 값이나 $b_1, b_2, \dots, b_m$의 값은 답에 영향이 없다.

$\frac{p_x}{n}$을 $998\,244\,353$으로 나눈 나머지를 구하는 과정, 즉 $p_x \equiv n \cdot z \pmod {998\,244\,353}$인 정수 $z$를 구하는 과정은 잘 알려져 있다. 가장 많이 쓰이는 방법은 페르마의 소정리와 분할 정복을 이용한 거듭제곱을 사용하는 방법이다. 페르마의 소정리에 의해, 어떤 소수 $p$에 대해 $\gcd(n, p) = 1$이면

$$n^{p-1} \equiv 1 \pmod p$$

이다. 따라서 $p_x \equiv p_x \cdot n^{p-1} \pmod p$이고, $z = p_x \cdot n^{p-2}$로 두면 된다. 이 문제의 경우 $p = 998\,244\,353$이고, 이는 소수임을 확인할 수 있다. $n^{p-2}$를 구하는 과정은 $p$의 값이 크므로 분할 정복을 이용한 거듭제곱을 사용해야 한다.

이제 답이 위와 같은 이유를 증명한다. 여러 가지 접근 방식이 존재하지만, 이 중 대칭성을 이용한 방식을 서술한다.

먼저 $n = c$이며 모든 색의 공이 정확히 한 개씩 존재한다고 가정하자. 이 경우 대칭성을 이용해 최종 공의 색이 $x$일 확률은 모든 $x \in \{1, 2, \dots, n\}$에 대해 $\frac{1}{n}$임을 쉽게 알 수 있다.

이제 일반적인 경우를 살펴보자. 같은 공의 색이 여러 개 존재할 수 있는데, 각각의 색을 세분화해 (원래 색, 인덱스)의 새로운 색으로 표기해 모든 공을 다른 색으로 나누어 주자. 예를 들어, 색이 $4$인 공이 세 개 존재한다면, 색 $(4, 1)$, 색 $(4, 2)$, 색 $(4, 3)$과 같이 나누어 주는 식이다. 이렇게 생각하고 나면, 최초에 존재하는 $n$개의 공이 모두 다른 색을 가지고 있다고 생각할 수 있다. 따라서 모든 시행이 끝나고 나면, 최초의 $n$가지 색 각각에 대해, 최종 공이 그 중 특정한 색을 가지고 있을 확률이 $\frac{1}{n}$임을 알 수 있다.

하지만 여기에서 나오는 순서쌍 형태의 색 $(a, b)$는 우리가 임의로 정한 색이고, 그 공의 실제 색은 $a$이다. 따라서, 최초에 색 $x$의 공이 $p_x$개 있었다면, 최종 공의 색이 $x$일 확률은 $\frac{p_x}{n}$이다.

이 문제의 상황은 마틴게일(martingale)과도 관련이 있다. 관심이 있는 독자는 관련 정보를 찾아보면 좋을 것이다.