N개의 방

$P=p_0+p_1+\cdots+p_N$라 하자. $E_i$를 과정이 끝나기 전까지 따스가 $i$번 방에서 머무르는 시간의 기댓값이라 하고, 편의를 위해 $E_{N+1}=0$으로 둔다.

$i$번 문을 기준으로 왼쪽에서 오른쪽으로 통과한 횟수를 $R_i$, 오른쪽에서 왼쪽으로 통과한 횟수를 $L_i$라 하자. 따스는 처음에는 $i$번 문의 왼쪽에 있고 마지막에는 오른쪽에 있으므로, 모든 시행에서

$$R_i-L_i=1$$

이 성립한다.

따스가 $i$번 방에 있는 매분마다 $i$번 문을 통해 오른쪽으로 이동할 확률은 $\frac{p_i}{P}$이다. 따라서

$$\mathbb E[R_i]=E_i\frac{p_i}{P}.$$

마찬가지로

$$\mathbb E[L_i]=E_{i+1}\frac{p_i}{P}.$$

두 식을 빼면

$$(E_i-E_{i+1})\frac{p_i}{P}=1$$

이므로

$$E_i-E_{i+1}=\frac{P}{p_i}$$

이다.

이를 $i$부터 $N$까지 더하고 $E_{N+1}=0$을 이용하면

$$E_i=P\sum_{k=i}^{N}\frac{1}{p_k}$$

를 얻는다.

따라서 모든 $p_i$의 모듈러 역원을 구한 뒤, 오른쪽에서 왼쪽으로 역원의 누적합을 관리하면 모든 답을 구할 수 있다.

각 역원을 페르마의 소정리로 따로 계산하면 $O(N\log 998244353)$에 해결할 수 있다. 더 빠르게는 모든 $p_i$의 누적곱을 만든 뒤 전체 곱의 역원을 한 번만 구하고 역순으로 진행하는 일괄 역원 계산을 사용하여 $O(N+\log 998244353)$에 해결할 수 있다.

Solution written by GPT5.6