Hướng dẫn giải của 30. Tổng tích lũy bậc thừa (RSUMF6 - * *) tr71

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

1. Tóm tắt đề bài

Tính giá trị biểu thức:

~F(n) = 1^2 \times 2 + 2^2 \times 3 + 3^2 \times 4 + \dots + n^2 \times (n + 1) = \sum_{i=1}^{n} i^2 \times (i + 1)~

  • Dữ liệu vào (Input): Số nguyên dương ~n~ (~1 \le n \le 10^4~).
  • Dữ liệu ra (Output): Kết quả của ~F(n)~ sau khi chia lấy dư cho ~MOD = 10^9 + 7~.

2. Phân tích bài toán & Giới hạn

  • Giới hạn ~n~: ~n \le 10^4~.

    * Với ~n \le 10^4~, số vòng lặp tối đa là ~10^4~ phép tính — cực kỳ nhỏ so với ngưỡng ~10^7 - 10^8~ thao tác/giây của hệ thống.

3. Thuật toán xử lý

  • Ý tưởng:

    1. Khởi tạo biến tổng ans = 0.
    2. Dùng biến lặp ~i~ chạy từ ~1~ đến ~n~.
    3. Tại mỗi bước lặp ~i~:
      • Tính số hạng thứ ~i~: ~T_i = i^2 \times (i + 1) \pmod{MOD}~.
      • Cộng dồn vào kết quả: ~ans = (ans + T_i) \pmod{MOD}~.
    4. Sau khi kết thúc vòng lặp, in ra giá trị ~ans~.

  • Độ phức tạp:

    • Thời gian: ~\mathcal{O}(n)~ — Thực thi trong chưa đầy ~0.01~ giây.
    • Không gian (bộ nhớ): ~\mathcal{O}(1)~.
Đang tải...