전체 풀이
다음 누적곱과 누적합을 구한다. 모든 계산은 으로 나눈 나머지에서 수행하며, 나눗셈은 모듈러 역원의 곱셈을 뜻한다.
이다. 쿼리 에 대해
를 계산하면, 답은
이다. 전처리 시간은 이고, 쿼리 하나를 에 처리한다. 따라서 전체 시간 복잡도는 이다.
입력된 확률은 이며 는 이상 이하의 정수이다. 이 가지 확률과 그 역원을 미리 구해 두면, 와 를 각각 한 번의 곱셈으로 갱신할 수 있다. 에는 가 아니라 를 더한다. 확률이 이 아니므로 필요한 역원은 모두 존재한다.
증명
길이가 인 덩어리 안에서 두 전구를 순서 있게 고르는 방법은 가지이다. 같은 전구를 두 번 고르는 것도 허용한다. 따라서 길이 제곱 합은 같은 덩어리에 속한 전구 순서쌍의 수이다.
인 두 위치가 같은 덩어리에 속하려면 번부터 번까지의 전구가 모두 켜져야 하고, 이것으로 충분하다. 각 전구가 켜지는 사건은 독립이므로 그 확률은
서브태스크 1
모든 전구가 반드시 켜진다. 쿼리 구간에는 길이 인 덩어리 하나가 있으므로 답은 이다. 입력을 읽는 시간을 포함해 에 처리한다.
이다. 인 경우에도 해당 전구가 켜져야 하므로 확률은 이다.
기댓값의 선형성에 의해, 인 쌍은 두 순서로 세고 인 쌍은 한 번만 세면 된다. 따라서
라고 하면 구하는 기댓값은 이다.
이제 오른쪽 끝 를 먼저 고정하여 합을 정리한다.
두 전구가 같은 덩어리에 속하는지는 그 사이의 전구만으로 결정된다. 쿼리 구간 밖의 전구가 켜졌는지에 대한 조건은 곱하지 않는다.
서브태스크 2
각 쿼리 구간의 길이를 이라 하자. 그 구간 안의 전구가 켜지거나 꺼지는 가지 상태를 모두 살펴본다. 각 상태의 발생 확률과 길이 제곱 합을 구해 곱한 뒤 더한다. 쿼리당 , 테스트 케이스당 이다.
서브태스크 3
쿼리 구간을 왼쪽부터 순서대로 처리한다. 지금까지 처리한 구간의 오른쪽 끝에서 연속해서 켜진 전구 수의 기댓값을 , 길이 제곱 합의 기댓값을 라 하자. 처음에는 이다.
새 전구가 켜지면 길이 인 마지막 덩어리의 길이가 이 되므로 길이 제곱 합은 만큼 늘어난다. 새 전구는 이전 전구들과 독립이므로
로 갱신한다. 첫 번째 식은 갱신하기 전의 를 사용한다. 쿼리 하나에 이 걸리며, 전체 시간 복잡도는 이다.
Solution written by GPT6
