Hướng dẫn cho Python Basic Contest #01 - Tổng các tích (Python only)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Sunlight

Lời giải

Subtask 1:

$n \le 100$

Bạn chỉ cần làm đúng những gì đề bài yêu cầu: duyệt qua mọi cặp $(i, j)$ và tính tích các số từ $a_i$ đến $a_j$ .

Độ phức tạp: $O(n^3)$ .

Subtask 2:

$n \le 1000$

Nhận xét rằng, ta có thể tận dụng kết quả của tích từ $a_i$ đến $a_{j - 1}$ để tính tích các số từ $a_i$ đến $a_j$ .
Như vậy, với mỗi $i$ , ban đầu ta đặt $t = 1$ và duyệt lần lượt $j$ từ $i + 1$ đến $n$ . Với mỗi $j$ ta nhân $t$ với $a_j$ và cộng kết quả cho $t$ .

Độ phức tạp $O(n^2)$ .

Subtask 3: Không có giới hạn gì thêm

Ký hiệu $F(i)$ là tổng các tích các dãy con kết thúc ở $i$ của dãy $a$ (ví dụ với $a = (1, 2, 3)$ thì $F(1) = 1$ , $F(2) = 1 \times 2 + 2$ , $F(3) = 1 \times 2 \times 3 + 2 \times 3 + 3$ ). Ta nhận thấy, kết quả bài toán sẽ là tổng các $F(i)$ với $1 \le i \le n$ .
Ta cũng nhận thấy rằng, $F(i)$ có thể được tính dựa trên $F(i - 1)$ thông qua một phép tính - việc tìm kiếm mối liên hệ giữa $F(i)$ và $F(i - 1)$ xin nhường lại cho bạn đọc

Độ phức tạp: $O(n)$ .

Bình luận

Không có bình luận nào.