Bedao Regular Contest 06 - EXAMS

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ở một ngôi trường nọ, có một quy tắc mà học sinh nào cũng biết đó là "ôn thi một đằng kiểm tra một nẻo".

Vào một ngày mưa rào, tâm tình gắt gỏng nên cô của Neko vừa cho ôn dạng bài tìm tích của ~2~ số thì đã cho làm bài kiểm tra và bắt Neko phải tìm ra được tổng của tích tất cả các bộ ~3~ số ~a_i, a_j, a_k~ trong ~n~ số ~(1 \le i < j < k \le n)~. Vì quá sốc văn hóa nên Neko đành phải nhờ bạn lập trình giải giúp bài toán này. Do kết quả có thể là số rất lớn nên Neko yêu cầu bạn phải lấy phần dư khi chia kết quả cho ~10^9 + 7~.

Input

  • Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, a_3, ..., a_n~ ~(1 \leq a_i \le 10^6)~.

Output

  • Ghi ra tổng của tích tất cả các bộ ~3~ số trong ~n~ số.

Sample Input

5
3 2 5 4 6

Sample Output

580

Subtask

  • ~10\%~ số test có ~n \le 500~ và ~a_i \le 10^4~
  • ~10\%~ số test tiếp theo có ~n \le 5000~
  • ~80\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


  • 0
    vominhmanh10  commented on Dec. 24, 2025, 4:22 a.m.

    bài toán được giải quyết trong O(n) với mảng cộng dồn:
    ta cần tính S(ai * aj * ak) (1 <= i < j < k <= n)

    1. Cố định (i, j) ta có: S(ai * aj * ak) = S(ai * aj) * S(ak), vì (j < k <= n) nên S(ak) = p[n] - p[j] (p là mảng cộng dồn)
    2. Cố định j ta có: S(ai * aj) * (p[n] - p[j]) = S(ai) * S(aj * (p[n] - p[j])), vì (1 <= i < j) nên S(ai) = p[j - 1]
    3. Vậy duyệt j và tính kết quả ans = (ans + (a[j] * (p[n] - p[j]) * p[j - 1])) % mod
    import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
S = [0] * (n + 1)
for i in range(1, n + 1): S[i] = S[i - 1] + a[i - 1]
ans = 0
for j in range(2, n): ans = (ans + (S[j - 1] * (S[n] - S[j]) * a[j - 1])) % mod
print(ans)

  • -1
    nongquan  commented on April 1, 2025, 3:51 p.m.

    https://ideone.com/NOmPtD


  • -4
    tiendungnguyen860  commented on Oct. 3, 2024, 8:20 a.m.

    ok


  • -8
    K32NGHIEMDUNG  commented on Aug. 29, 2024, 9:03 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -13
    2004_TranNgoNamCuong  commented on Aug. 12, 2024, 2:31 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.