Tóm tắt đề bài

Cho dãy số nguyên \(A\) gồm \(N\) phần tử. Yêu cầu tính tổng của tất cả các tích \(A[i] \times A[j]\) với mọi cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j \le N\).

Công thức cần tính:

Phân tích

• Giới hạn: \(N \le 10^6\) và \(|A[i]| \le 10^6\).
• Độ phức tạp ngây thơ: Nếu sử dụng hai vòng lặp lồng nhau để tính tổng theo công thức trên, độ phức tạp sẽ là \(O(N^2)\). Với \(N = 10^6\), \(N^2 = 10^{12}\), cách tiếp cận này sẽ bị quá thời gian (TLE).
• Nhận xét quan trọng: Ta có thể biến đổi biểu thức để tối ưu hóa việc tính toán. Dựa vào tính chất phân phối của phép nhân đối với phép cộng:
  • Với \(i=1\), các tích là: \(A[1] \times A[2] + A[1] \times A[3] + \dots + A[1] \times A[N] = A[1] \times (A[2] + A[3] + \dots + A[N])\)
  • Với \(i=2\), các tích là: \(A[2] \times A[3] + A[2] \times A[4] + \dots + A[2] \times A[N] = A[2] \times (A[3] + A[4] + \dots + A[N])\)
  • Tổng quát, với mỗi \(i\), ta cần nhân \(A[i]\) với tổng của các phần tử đứng sau nó.

Hướng giải quyết

Sử dụng mảng cộng dồn (Prefix Sum)

Để tính nhanh tổng các phần tử trong một đoạn, ta sử dụng kỹ thuật mảng cộng dồn.

1. Gọi \(S[i]\) là tổng của \(i\) phần tử đầu tiên: \(S[i] = A[1] + A[2] + \dots + A[i]\).
2. Tổng các phần tử từ vị trí \(i+1\) đến \(N\) sẽ là: \(S[N] - S[i]\).
3. Khi đó, kết quả bài toán là:
   
   \[ \text{kq} = \sum_{i=1}^{N-1} A[i] \times (S[N] - S[i]) \]

Các bước thực hiện

1. Đọc dữ liệu \(N\) và dãy \(A\).
2. Xây dựng mảng cộng dồn \(S\) với \(S[i] = S[i-1] + A[i]\).
3. Duyệt \(i\) từ \(1\) đến \(N-1\), cộng dồn giá trị \(A[i] \times (S[N] - S[i])\) vào biến kết quả.
4. In kết quả cuối cùng.

Lưu ý về kiểu dữ liệu: Vì \(A[i]\) lên tới \(10^6\) và \(N\) lên tới \(10^6\), kết quả trung gian và kết quả cuối cùng có thể vượt quá giới hạn của số nguyên 32-bit (int trong C++). Cần sử dụng số nguyên 64-bit (long long trong C++ hoặc mặc định int trong Python 3) để lưu trữ.

Độ phức tạp

• Thời gian: \(O(N)\) để tính mảng cộng dồn và \(O(N)\) để tính tổng các tích. Tổng cộng là \(O(N)\).
• Bộ nhớ: \(O(N)\) để lưu trữ mảng \(A\) và mảng cộng dồn \(S\).

Code tham khảo

Python

import sys

def solve():
    # Đọc N
    line1 = sys.stdin.readline()
    if not line1:
        return
    n = int(line1.strip())

    # Đọc mảng A
    a = list(map(int, sys.stdin.read().split()))

    # Tạo mảng cộng dồn S
    # S[i] lưu tổng của i phần tử đầu tiên
    s = [0] * (n + 1)
    for i in range(1, n + 1):
        s[i] = s[i-1] + a[i-1]

    kq = 0
    # Duyệt qua từng phần tử a[i-1] (tương ứng A[i] trong công thức)
    # Nhân nó với tổng các phần tử đứng sau nó: S[n] - S[i]
    for i in range(1, n):
        kq += a[i-1] * (s[n] - s[i])

    print(kq)

if __name__ == "__main__":
    solve()

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> a(n);
    vector<long long> s(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }

    long long kq = 0;
    for (int i = 0; i < n - 1; i++) {
        // a[i] nhân với tổng các phần tử từ a[i+1] đến a[n-1]
        // Tổng đó bằng s[n] - s[i+1]
        kq += a[i] * (s[n] - s[i + 1]);
    }

    cout << kq << endl;

    return 0;
}