Informatica Online Judge

  클릭 클릭 팡팡 (Insane) [1698 / 06A2]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs15053 - ms / 851byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 백인규)]

Background

동현이는 마침내 "클릭클릭 팡팡"이라는 모바일 게임을 출시했다.

게임은 총 $N$개의 버블을 박자에 맞춰 순서대로 터뜨리는 방식으로 진행된다.

정확한 박자에 버블을 터뜨리면 콤보가 $1$ 올라간다. 타이밍을 맞추지 못해 터뜨리는 데 실패한 경우, 지금까지의 콤보의 세제곱이 점수에 더해지고, 콤보 카운트는 $0$이 된다. 게임이 끝난 직후에도 콤보의 세제곱이 점수에 더해진다.

다시 말해, 각 버블의 성공/실패 결과를 나타내는 "O"와 "X"로 이루어진 길이 $N$인 문자열을 생각하고, 그 문자열에서 연속된 "O"들을 하나의 집합으로 묶으면, 각 집합의 크기의 세제곱의 합이 최종 점수가 된다.

그런데, 동현이의 게임이 마음에 들지 않았던 현수는 서버를 해킹해, 콤보의 M제곱이 점수에 더해지도록 점수 계산 방식을 바꿔 버렸다. ($M$은 자연수이다.)

그 후, 현수는 동현이에게 다음과 같은 제안을 했다.

"네가 $i$번째 버블을 터뜨리는 데 성공할 확률이 $P_i$일 때, 너의 최종 점수의 기댓값을 계산할 수 있다면 해킹을 중단하지."

빨리 구하는 게 좋을 거야, 당신.

Input

첫째 줄에는 버블의 수 $N$과 현수가 정한 자연수 $M$이 주어진다.

둘째 줄에는 $i$번째 버블을 터뜨리는 데 성공할 확률 $P_i$들이 실수로 주어진다.

(단, 게임에서 얻을 수 있는 최대 점수는 $4.0×10^{18}$ 을 넘어가지 않는다.)

[입력값의 정의역]

$1 ≤ N ≤ 200,000$
$1 ≤ M ≤ 8$
$M ≠ 3$
$1 ≤ i ≤ N$
$0 ≤ P_i ≤ 1$

Output

최종 점수의 기댓값을 소수점 이하 3자리까지 출력한다.

IO Example

입력1
3 2
0.5 0.5 0.5

출력1
2.750

입력2
4 7
0.1 0.2 0.3 0.4

출력2
113.291

설명
첫 번째 예제에서 게임의 결과는 총 8가지가 있으며, 확률은 모두 0.125로 같다. 각 결과의 점수를 모두 더하고 8로 나누면 점수의 기댓값은 2.75점임을 알 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]