Editorial for Bedao Regular Contest 06 - EXAMS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Ta có thể tiếp cận bài này bằng hai cách như sau:

Toán

Gọi ~P~ là tổng của tích các cặp ~a_i \times a_j~ với ~(i < j)~, ~S~ là tổng tất cả các ~a_i~ với ~(1 \le i \le n)~

Ta để ý rằng ~P~ hoàn toàn có thể được tính nhanh trong ~O(n)~ theo công thức sau đây:

  • ~P = \frac{1}{2} \times ((\sum\limits_{i=1}^{n} a_i)^2 - \sum\limits_{i=1}^{n} a_i^2)~
  • ~S = \sum\limits_{i=1}^{n} a_i~

Như vậy kết quả bài toán sẽ là ~\frac{1}{3} \times \sum\limits_{i=1}^{n} (a_i \times P - a_i^2 \times (S - a_i))~

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

Quy hoạch động

Gọi ~f_{i, j}~ là tổng các bộ tích có ~j~ phần tử và phần tử cuối nằm ở vị trí ~i~ ~(1 \le j \le 3, 1 \le i \le n)~

  • ~f_{i, 1} = f_{i - 1, 1} + a_i~ với ~(1 \le i \le n)~
  • ~f_{i, j} = f_{i - 1, j} + f_{i - 1, j - 1} \times a_i~ với ~(1 \le i \le n, 2 \le j \le 3)~

Như vậy kết quả bài toán sẽ là ~f_{n, 3}~

Độ phức tạp: ~O(2 \times n)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.