문제 : https://arca.live/b/math/45513676
요약하면, 문자열 끝에 1을 추가하는 쿼리, 문자열 끝에 -를 추가하는 쿼리 그만두는 쿼리 세 가지가 있다. 문자열은 1진법으로 해석되고, - 부호가 여러 개 있으면, 두 개 쌍은 상쇄된다.
이 쿼리들로 수행된 최종 문자열은 다음과 같은 성질을 가진다.
(1) : 하나 이상의 1 (또는 0)이 존재한다.
(2) : 0개 이상의 -가 존재한다.
문자열을 앞에서부터 분석해보자.
문자열 제일 앞에 + 부호가 붙어있다고 가정하자. 이 +는 -와 만나면 -를 유지하고 +만 사라진다고 하자. 즉, 문자열의 가장 앞은 부호를 나타내는 기호가 항상 있다고 가정하자.
이때 (1) 성질에 의해 문자열 제일 앞의 부호부터 시작해서 가장 처음 나오는 1 (또는 0) 이전까지의 연속된 부호의 개수를 셀 수 있다. 그리고, 그 1 (또는 0)부터, 문자열이 끝나거나 다른 -가 나올 때까지의 1 (또는 0)의 개수를 셀 수 있다.
이렇게 문자열을 부호-숫자의 세트로 항상 분리할 수 있다. 문자열은 항상 0 또는 1로 끝나며 + 또는 -로 끝나기 때문이다.
부호-숫자 세트는 항상 상호 독립이므로 각각의 기대값을 더한 값이 총 기대값이 된다.
현재 부호로 끝난 문자열이 있다고 가정하자. (이 부호는 +일수도 있다.) 쿼리가 끝나지 않았다고 가정하자. 이때 새로 추가되는 문자의 종류에는 1, -, 0 중 하나가 올 수 있다. 뒤에 0이 추가되는 경우, 이 부호 세트를 포함하여 이 이후의 값은 수식의 값에 영향을 주지 않는다. 즉, 이 부호-숫자 세트의 기대값은 0이다.
-와 1의 분포는 부호로 종료되지 않는다고 가정해도 좋으므로, (부호로 종료되는 경우 0이므로) 각 분포는 기하분포를 따른다. 이중 첫 부호 세트는 0개 이상의 부호, 나머지 숫자와 부호 세트는 1개 이상의 문자를 가진다. 각 부호 세트의 부호 개수가 짝수일 확률과 홀수일 확률을 기하분포의 확률질량함수로 구해보면 확률이 0.5인 기하분포이므로 동일하다. 즉, 부호-숫자 세트의 부호에 대한 기대는 반반이다. 마찬가지로 첫 부호 세트도 동일하게 반반의 기대를 가진다.
숫자 세트는 부호 세트에 독립이므로 고유한 숫자 분포 X를 가질 때 부호-숫자 세트의 기대값은 P(+)E[X]-P(-)E[X] = 0이다.
따라서, 어떤 부호-숫자 세트의 기대값도 0이고, 따라서 수식의 값 또한 부호-숫자 세트의 합의 기대값과 같으므로 0이다.
