BOJ 33470 수열과 쿼리와 확률 2

Problems

문제 링크:

문제 내용

길이 $N$ 의 수열 $A = A_1, A_2, \cdots, A_N$ 이 주어집니다. 여기에 다음 $N+1$ 종류의 연산 중 하나를 무작위로 총 $M$ 번 수행합니다.

$i$ 번 연산( $1 \le i \le N$ )은 $A_i$ 를 $A_i \times i$ 로 변경합니다.
$N+1$ 번 연산은 모든 $1 \le i \le N$ 에 대해 $A_i$ 를 $A_i \times (N + 1 - i)$ 로 변경합니다.

각 연산은 독립적으로 정해지며, 각 연산이 뽑힐 확률은 서로 같습니다.

이때 다음의 두 종류의 질문에 대해 답을 출력하세요.

S: 초기 상태에서 원소의 합을 $S_0$ , 최종 상태에서 원소의 합을 $S_1$ 이라고 할 때 $\frac{S_1}{S_0}$ 의 기댓값
P: 초기 상태에서 원소의 곱을 $P_0$ , 최종 상태에서 원소의 곱을 $P_1$ 이라고 할 때 $\frac{P_1}{P_0}$ 의 기댓값

문제 풀이

스포일러

S 질문에 대한 답을 먼저 구해 봅시다.

1회의 연산을 수행했을 때, 각각의 $A_i$ 는 $\frac{1}{N+1}$ 의 확률로 $i$ , $\frac{1}{N+1}$ 의 확률로 $N+1-i$ 가 곱해지며, 그 외에는 값이 바뀌지 않습니다. 그 결과의 기댓값은 $(\frac{i}{N+1} + \frac{N+1-i}{N+1} + \frac{N-1}{N+1})A_i = \frac{2N}{N+1} A_i$ 입니다. 이 과정을 $M$ 번 수행하면 기댓값에 $\frac{2N}{N+1}$ 이 $M$ 번 곱해집니다. 이는 2번 정도 적용하였을 때 모든 결과와 확률을 나열하고 이를 가지고 기댓값을 계산한 다음, 이를 인수분해하여 확인할 수 있습니다.

최종 상태에서 원소의 합의 기댓값은 기댓값의 선형성에 의해 최종 상태에서 각 원소의 기댓값의 합과 같으므로, $\frac{S_1}{S_0} = (\frac{2N}{N+1})^M$ 을 얻습니다.

P 질문에 대한 답은 전체의 곱이 어떻게 바뀌는지로 알 수 있습니다. 비슷하게 분석해보면, 1회의 연산을 수행하였을 때 전체 곱은 $\frac{1}{N+1}$ 의 확률로 $N!$ 배, $\frac{1}{N+1}$ 의 확률로 $1, 2, \cdots, N$ 배가 됩니다. 그 결과의 기댓값은 $(\frac{N!}{N+1} + \frac{\sum i}{N+1}) P_0$ 이 됩니다. 역시 독립적으로 $M$ 번 수행했을 때의 기댓값은 $(\frac{N!}{N+1} + \frac{\sum i}{N+1})^M P_0$ 이 됩니다.

$M$ 이 크고 모듈로가 소수이므로 분할정복 거듭제곱과 페르마 소정리를 이용하여 답을 구할 수 있습니다.

Last updated on 2025년 9월 18일 17:33:13

BOJ 33365 Password BOJ 33741 actGenshinImp