Bàn Ăn Ngẫu Nhiên · canuc80k5508 · Thuật toán Canuc80k

Trên bàn có $N$ đĩa, được đánh số từ $1$ đến $N$ . Ban đầu, đĩa $i$ chứa $a_{i}$ miếng thức ăn, trong đó mỗi $a_{i}$ thuộc tập ${1, 2, 3}$ .

Một lượt diễn ra như sau:

Chọn đều ngẫu nhiên một trong toàn bộ $N$ đĩa.
Nếu đĩa được chọn còn ít nhất một miếng, ăn đúng một miếng trên đĩa đó.
Nếu đĩa đã rỗng, lượt này không làm thay đổi trạng thái bàn ăn.

Các lượt được lặp lại cho đến khi mọi đĩa đều rỗng. Hãy tính kỳ vọng của tổng số lượt đã thực hiện.

Input

Dòng đầu chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ .

Output

In một số thực là kỳ vọng số lượt cần thiết. 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^{- 9}$ .

Constraints

$1 \leq N \leq 300$ .
$1 \leq a_{i} \leq 3$ với mọi $i$ .

Scoring

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

Example

Test 1

Input

2
1 2

Output

4.500000000000

Giải thích: Nếu ăn miếng trên đĩa một miếng trước, trạng thái còn lại cần kỳ vọng $4$ lượt; nếu ăn trên đĩa hai miếng trước, trạng thái còn lại cần kỳ vọng $3$ lượt. Lượt đầu luôn có ích, nên tổng kỳ vọng là $1 + (4 + 3) /2 = 4.5$ .

Hướng giải: Không cần biết đĩa nào mang số hiệu gì; chỉ cần biết hiện có bao nhiêu đĩa còn 1, 2 và 3 miếng. Gọi trạng thái đó là (x,y,z) và gọi E(x,y,z) là kỳ vọng số lượt còn lại.
Hướng giải: Có x+y+z đĩa chưa rỗng. Nếu chọn trúng đĩa rỗng, trạng thái không đổi. Chuyển hạng tử tự lặp này sang vế trái cho ta
Hướng giải:

text E(x,y,z) = N/(x+y+z) + x/(x+y+z) * E(x-1,y,z) + y/(x+y+z) * E(x+1,y-1,z) + z/(x+y+z) * E(x,y+1,z-1). - Hướng giải: Mỗi trạng thái ở vế phải có tổng số miếng ít hơn đúng 1. Vì vậy có thể tính theo tổng số miếng tăng dần. - Hướng giải: Để giảm bộ nhớ, xét một lớp có tổng số miếng s. Khi biết y và z, số đĩa một miếng được xác định duy nhất bởi - Hướng giải:

text x = s - 2y - 3z. - Hướng giải: Do mọi chuyển tiếp chỉ đi về lớp s-1, ta chỉ giữ hai bảng hai chiều cho lớp trước và lớp hiện tại. Trạng thái rỗng có kỳ vọng 0. - Chứng minh đúng: Ba số (x,y,z) xác định đầy đủ xác suất của mọi kết quả ở lượt tiếp theo, nên chúng tạo thành một trạng thái Markov hợp lệ. Phân hoạch theo loại đĩa được chọn cho phương trình kỳ vọng ở trên; phần chọn trúng đĩa rỗng đã được khử đại số, vì thế hệ số tự lặp không còn xuất hiện. - Chứng minh đúng: Mỗi trạng thái phụ thuộc duy nhất vào các trạng thái có ít hơn một miếng. Theo quy nạp trên tổng số miếng, khi thuật toán tính lớp s, mọi giá trị ở lớp s-1 đã đúng. Thay các giá trị đó vào phương trình cho đúng E(x,y,z). Do đó trạng thái ban đầu cũng được tính đúng. - Độ phức tạp: Có O(N^3) trạng thái hợp lệ. Mỗi trạng thái được xử lý trong O(1), nên thời gian là O(N^3). Hai lớp DP chứa O(N^2) phần tử, nên bộ nhớ là O(N^2).