Elearning CodePath – CTP Online Judge

Tổng các tích đặc biệt

MULARR

🟢 Easy #Prefix Sum

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Yêu cầu

Cho dãy $A$ gồm $N$ phần tử số nguyên. Yêu cầu tìm tổng các tích của mỗi phần tử $A[i]$ với các phần tử $A[j]$ với mọi $j > i$.

Công thức tính toán:
$\text{Result} = \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} A[i] \cdot A[j]$

---
### 📝 Bài toán

Tính giá trị của biểu thức $\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} A[i] \cdot A[j]$.

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

* Dòng đầu ghi số $N$ (độ dài dãy, $N \le 10^6$).
* Dòng tiếp theo ghi $N$ số nguyên $A_0, A_1, \dots, A_{N-1}$, các số cách nhau bởi dấu cách.

Giới hạn:
* $N \le 10^6$.
* $|A[i]| \le 10^6$. (Lưu ý: Đề bài ghi $A[i] \le 10^6$, nhưng không rõ có thể âm hay không, ta giả định có thể âm nếu không có ràng buộc chặt).

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

Ghi một số là kết quả của bài toán.

---
### ✨ Ví dụ

| Input | Output | Giải thích VD |
| :---: | :---: | :--- |
| `4` <br> `9 3 4 2` | `107` | Tích = $(9 \cdot 3 + 9 \cdot 4 + 9 \cdot 2) + (3 \cdot 4 + 3 \cdot 2) + (4 \cdot 2) = 107$ |

---
### 🏷 Ràng buộc

Giới hạn $N \le 10^6$ yêu cầu thuật toán $O(N)$.

| Subtask | Ràng buộc $N$ (Giả định) | Kỹ thuật (Giả định) | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | $N \le 1000$ | $O(N^2)$ (Duyệt mọi cặp $(i, j)$) | $30\%$ |
| $2$ | $N \le 10^6$ | $O(N)$ (Biến đổi công thức / Prefix Sum) | $70\%$ |

---

✅ Đã AC: 0 / 0 submissions