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

Cho số nguyên dương ~n~. Hãy tính tổng:

~ S = 1^1 + 2^2 + 3^3 + \dots + n^n = \sum_{i=1}^{n} i^i ~

Vì kết quả tăng rất nhanh, in ra kết quả theo modulo ~MOD = 10^9 + 7~.

• Dữ liệu vào (Input): Số nguyên dương ~n~ (~1 \le n \le 10^3~).
• Dữ liệu ra (Output): Giá trị của ~S \pmod{10^9 + 7}~.

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

• Giới hạn ~n~: ~n \le 10^3~.
• Giá trị ~i^i~ tăng theo hàm mũ cực nhanh và sớm vượt qua giới hạn của kiểu dữ liệu 64-bit thông thường ngay từ khi ~i \ge 15~. Do đó, ta bắt buộc phải thực hiện phép chia lấy dư modulo ở từng phép nhân.
• Với ~n \le 10^3~, ta có thể duyệt tuần tự từng số hạng ~i^i~ từ ~i = 1~ đến ~n~. Tại mỗi số hạng, tính giá trị ~i^i \pmod{MOD}~ bằng vòng lặp nhân dồn thông thường hoặc lũy thừa nhanh (nhị phân).

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

• Ý tưởng:

  1. Khởi tạo biến lưu tổng kết quả: ans = 0.
  2. Duyệt biến ~i~ chạy từ ~1~ đến ~n~:
     • Tính giá trị ~T_i = i^i \pmod{MOD}~:
       • Có thể dùng vòng lặp nhân ~i~ liên tiếp ~i~ lần, sau mỗi phép nhân đều lấy dư cho ~MOD~.
       • Hoặc tối ưu hơn bằng thuật toán lũy thừa nhị phân tính ~a^b \pmod{MOD}~.
     • Cộng dồn vào kết quả: ans = (ans + T_i) % MOD.
  3. Sau khi kết thúc vòng lặp, in ra giá trị ans.

• Độ phức tạp:

  • Thời gian:
    • Dùng vòng lặp nhân thông thường: ~\mathcal{O}(n^2)~ — với ~n \le 10^3~, số phép tính khoảng ~\frac{n(n + 1)}{2} \approx 5 \times 10^5~ phép toán, chạy cực nhanh trong thời gian ~< 0.02~ giây.
    • Dùng lũy thừa nhị phân: ~\mathcal{O}(n \log n)~ — tối ưu hơn, hoàn toàn xử lý tốt kể cả khi mở rộng ~n \le 10^5~.
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~.