Nhịp Thành Công · canuc80k5506 · Thuật toán Canuc80k

Có $n$ lượt thử độc lập, được thực hiện theo thứ tự từ $1$ đến $n$ . Lượt thứ $i$ thành công với xác suất $p_{i}$ và thất bại với xác suất $1 - p_{i}$ .

Sau khi tất cả lượt thử kết thúc, ta chia các lượt thành công thành những đoạn liên tiếp cực đại. Nếu độ dài các đoạn đó lần lượt là $l_{1}, l_{2}, \dots, l_{k}$ , điểm của kết quả được định nghĩa là

l_{1}^{2} + l_{2}^{2} + \dots + l_{k}^{2} .

Nếu không có lượt nào thành công thì điểm bằng $0$ . Hãy tính kỳ vọng của số điểm.

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số thực $p_{1}, p_{2}, \dots, p_{n}$ . Mỗi số có không quá sáu chữ số sau dấu chấm thập phân.

Output

In một số thực là kỳ vọng của số điểm. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá $1 0^{- 6}$ .

Constraints

$1 \leq n \leq 1 0^{5}$ .
$0 \leq p_{i} \leq 1$ với mọi $1 \leq i \leq n$ .
Các lượt thử độc lập với nhau.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 18$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
1 0.5 0.5 0

Output

4.000000000000

Giải thích: Hai lượt giữa tạo bốn trường hợp đồng xác suất. Các điểm tương ứng là $1, 2, 4$ và $9$ , nên kỳ vọng bằng $(1 + 2 + 4 + 9) /4 = 4$ .

Hướng giải: Gọi L là độ dài đoạn thành công đang kết thúc ngay trước lượt hiện tại. Ta chỉ cần lưu kỳ vọng của L, ký hiệu là E[L].
Hướng giải: Nếu lượt mới thất bại, đoạn hiện tại bị ngắt và độ dài mới bằng 0. Nếu lượt mới thành công, độ dài tăng từ L thành L+1. Vì lượt mới độc lập với quá khứ,
Hướng giải:

text E[L_mới] = p_i * (E[L] + 1). - Hướng giải: Khi một lượt thành công nối vào đoạn dài L, đóng góp của đoạn đó trong tổng bình phương thay đổi từ L^2 thành (L+1)^2. Phần điểm tăng thêm là - Hướng giải:

text (L+1)^2 - L^2 = 2L + 1. - Hướng giải: Do đó kỳ vọng phần điểm tăng ở lượt i là - Hướng giải:

text p_i * (2E[L] + 1). - Hướng giải: Ta cộng lượng này vào đáp án, rồi cập nhật kỳ vọng độ dài đoạn hiện tại. - Chứng minh đúng: Xét một kết quả cố định của các lượt trước lượt i, với đoạn thành công cuối cùng có độ dài L. Nếu lượt i thất bại thì điểm không tăng. Nếu lượt i thành công, đoạn cuối được kéo dài thêm một và tổng bình phương tăng đúng 2L+1. Vì xác suất thành công là p_i, kỳ vọng gia tăng có điều kiện bằng p_i(2L+1). - Chứng minh đúng: Lấy kỳ vọng theo mọi kết quả của phần tiền tố và dùng tính độc lập, ta được gia tăng kỳ vọng p_i(2E[L]+1). Công thức cập nhật E[L_mới]=p_i(E[L]+1) cũng theo cùng hai trường hợp thành công/thất bại. Khởi đầu cả hai kỳ vọng đều bằng 0; sau khi xử lý lần lượt mọi lượt, tổng các gia tăng chính là kỳ vọng điểm cuối cùng. - Độ phức tạp: Thuật toán duyệt dãy xác suất đúng một lần, mất O(n) thời gian và O(1) bộ nhớ phụ.