Light Bulb Queries 2

전체 풀이

다음 누적곱과 누적합을 구한다. 모든 계산은 $M=998\,244\,353$으로 나눈 나머지에서 수행하며, 나눗셈은 모듈러 역원의 곱셈을 뜻한다.

$$C_0=1,\qquad C_i=\prod_{j=1}^{i}P_j$$ $$R_i=\sum_{j=1}^{i}C_{j-1}^{-1},\qquad U_i=\sum_{j=1}^{i}C_jR_j,\qquad V_i=\sum_{j=1}^{i}C_j,\qquad W_i=\sum_{j=1}^{i}P_j.$$

$R_0=U_0=V_0=W_0=0$이다. 쿼리 에 대해

$$H(l,r)=(U_r-U_{l-1})-R_{l-1}(V_r-V_{l-1})$$

를 계산하면, 답은

$$2H(l,r)-(W_r-W_{l-1})$$

이다. 전처리 시간은 $O(N)$이고, 쿼리 하나를 $O(1)$에 처리한다. 따라서 전체 시간 복잡도는 $O(N+Q)$이다.

입력된 확률은 $P_i=\cfrac{a_i}{100}$이며 $$는 이상 이하의 정수이다. 이 가지 확률과 그 역원을 미리 구해 두면, 와 를 각각 한 번의 곱셈으로 갱신할 수 있다. 에는 가 아니라 를 더한다. 확률이 이 아니므로 필요한 역원은 모두 존재한다.

증명

길이가 $L$인 덩어리 안에서 두 전구를 순서 있게 고르는 방법은 $L^2$가지이다. 같은 전구를 두 번 고르는 것도 허용한다. 따라서 길이 제곱 합은 같은 덩어리에 속한 전구 순서쌍의 수이다.

$l\leq a\leq b\leq r$인 두 위치가 같은 덩어리에 속하려면 번부터 번까지의 전구가 모두 켜져야 하고, 이것으로 충분하다. 각 전구가 켜지는 사건은 독립이므로 그 확률은

서브태스크 1

모든 전구가 반드시 켜진다. 쿼리 구간에는 길이 $r-l+1$인 덩어리 하나가 있으므로 답은 $(r-l+1)^2$이다. 입력을 읽는 시간을 포함해 에 처리한다.