Hướng dẫn giải

Hình vuông gồm các hàng ~i..i+k-1~ và các cột ~j..j+k-1~, tổng cần tính theo modulo ~20242025~.

Sub 1: Cộng trực tiếp — ~O(k^2)~, dùng khi ~k \le 1000~

Duyệt hai vòng lặp qua mọi ô ~(r, c)~ của hình vuông, cộng ~r \cdot c~ vào tổng modulo ~20242025~. Nếu chỉ nộp sub này: đúng 15/20 test (5 test có ~k~ lớn bị quá thời gian).

Sub 2: Công thức — ~O(1)~

Vì ~\sum_{r}\sum_{c} r \cdot c = \left(\sum_r r\right)\left(\sum_c c\right)~, và mỗi tổng là cấp số cộng: ~\sum_r r = k \cdot i + k(k-1)/2~, ~\sum_c c = k \cdot j + k(k-1)/2~. Với ~k \le 10^9~ thì ~k(k-1)/2 \le 5 \times 10^{17}~ vẫn nằm trong long long; lấy modulo từng tổng rồi mới nhân (tích hai số nhỏ hơn ~2 \times 10^7~ vừa long long). Nếu chỉ nộp sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

main đọc ~i, j, k~; ~k \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 20242025;
long long I, J, K;

// Sub 1: cộng trực tiếp k*k ô, O(k^2)
void sub1() {
    long long T = 0;
    for (long long r = I; r < I + K; r++)
        for (long long c = J; c < J + K; c++)
            T = (T + r * c) % MOD;
    cout << T << "\n";
}

// Sub 2: tổng = (tổng các hàng) * (tổng các cột), mỗi tổng là cấp số cộng, O(1)
void sub2() {
    long long sr = (K * I + K * (K - 1) / 2) % MOD; // K*(K-1)/2 <= 5e17, vừa long long
    long long sc = (K * J + K * (K - 1) / 2) % MOD;
    cout << sr * sc % MOD << "\n";
}

int main() {
    freopen("HVUONG.INP", "r", stdin);
    freopen("HVUONG.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> I >> J >> K;
    if (K <= 1000) sub1();
    else sub2();
}