Elearning CodePath – CTP Online Judge

Yet Another Prefix Sum Problem

G36

🟢 Easy #Prefix Sum

### Thông tin chung

| Tên bài toán | Câu lạc bộ của Homer (Homer's Clubs) |
| --- | --- |
| **Dữ liệu vào** | Số nguyên $m$ và mảng $a$ gồm $m$ phần tử |
| **Dữ liệu ra** | Một số nguyên duy nhất (kết quả sau khi modulo $998244353$) |

---

### Bài toán

Tại trường của Homer, có $n$ học sinh yêu thích các câu lạc bộ. Ban đầu, có $m$ câu lạc bộ, và mỗi học sinh thuộc duy nhất một câu lạc bộ. Cụ thể, câu lạc bộ thứ $i$ có $a_i$ học sinh ($1 \le i \le m$) và tổng số học sinh là $\sum_{i=1}^m a_i = n$.

Các học sinh này không thân thiện đến mức mỗi ngày, có đúng một học sinh (được chọn **ngẫu nhiên đồng nhất** từ $n$ học sinh) sẽ trở nên tức giận. Học sinh này sẽ thực hiện một trong hai hành động sau với xác suất ngang nhau ($\frac{1}{2}$):

1. **Tạo câu lạc bộ mới:** Với xác suất $\frac{1}{2}$, học sinh đó rời khỏi câu lạc bộ hiện tại, tự tạo một câu lạc bộ mới và gia nhập vào đó. Câu lạc bộ mới này lúc này chỉ có duy nhất một thành viên là chính học sinh đó.
2. **Gia nhập câu lạc bộ cũ:** Với xác suất $\frac{1}{2}$, học sinh đó không tạo câu lạc bộ mới. Thay vào đó, học sinh này rời câu lạc bộ hiện tại và chọn gia nhập vào một câu lạc bộ bất kỳ đang tồn tại (có thể chính là câu lạc bộ vừa rời đi) với xác suất tỉ lệ thuận với số lượng học sinh hiện có trong câu lạc bộ đó.
  - **Cụ thể:** Giả sử có $k$ câu lạc bộ với số lượng học sinh tương ứng là $b_i$ ($1 \le i \le k$) **trước khi** học sinh đó tức giận. Sau khi rời câu lạc bộ cũ, học sinh này sẽ vào câu lạc bộ thứ $i$ với xác suất là $\frac{b_i}{n}$.

**Lưu ý:** Nếu một câu lạc bộ trở nên trống rỗng (0 thành viên), các học sinh sẽ không bao giờ gia nhập lại câu lạc bộ đó nữa vì xác suất gia nhập (tỉ lệ thuận với 0) sẽ luôn bằng 0.

Homer muốn tính **giá trị kỳ vọng** của số ngày cho đến khi tất cả $n$ học sinh lần đầu tiên cùng thuộc về một câu lạc bộ duy nhất.

Kết quả cần được tính dưới dạng $p \cdot q^{-1} \pmod{998244353}$, trong đó $\frac{p}{q}$ là phân số tối giản của giá trị kỳ vọng. Các ràng buộc đảm bảo rằng $q \pmod{998244353} \neq 0$.

---

### Định dạng Đầu vào

- Dòng đầu tiên chứa số nguyên $m$ ($1 \le m \le 1000$) — số lượng câu lạc bộ ban đầu.
- Dòng thứ hai chứa $m$ số nguyên $a_1, a_2, \dots, a_m$ ($1 \le a_i \le 4 \cdot 10^8$) — số lượng học sinh ban đầu trong mỗi câu lạc bộ.
- Tổng số học sinh $n = \sum a_i$ thỏa mãn $1 \le n \le 4 \cdot 10^8$.

---

### Định dạng Đầu ra

- In ra một số nguyên duy nhất là giá trị kỳ vọng cần tìm theo modulo $998244353$.

---

### Ràng buộc

- $1 \le m \le 1000$
- $1 \le a_i \le 4 \cdot 10^8$
- $1 \le \sum a_i \le 4 \cdot 10^8$
- Modulo hệ thống: $998244353$

---

### Ví dụ

| Input | Output | Giải thích |
| --- | --- | --- |
| `2` <br> `1 1` | `4` | Với 2 học sinh ở 2 CLB, kỳ vọng sau 4 ngày họ sẽ về cùng 1 CLB. |
| `3` <br> `1 1 1` | `12` | Kỳ vọng số ngày để 3 học sinh về cùng 1 CLB là 12. |
| `1` <br> `10` | `0` | Đã thỏa mãn điều kiện ngay từ đầu. |

✅ Đã AC: 1 / 1 submissions