Hiểu bài toán

Bài toán yêu cầu đếm số lượng hình vuông có thể tạo thành từ một lưới hình vuông cạnh N. Lưới này được tạo bởi NxN ô vuông đơn vị. Ta cần đếm tất cả các hình vuông khác nhau (với các kích thước và vị trí khác nhau) có thể tìm thấy trong lưới đó. Kết quả cần in ra số dư khi chia cho 10^9 + 7. Ví dụ, với N=2, ta có 5 hình vuông (1 hình vuông 2x2, 4 hình vuông 1x1).

Các cách tiếp cận

Cách Công thức toán học

#include <iostream>
using namespace std;
typedef long long ll;
ll MOD = 1e9 + 7;
ll INV6 = 166666668; 
int main()
{
    ll n;
    cin >> n;
    ll a = n % MOD;
    ll b = (n + 1) % MOD;
    ll c = (2 * n + 1) % MOD;
    ll result = a * b % MOD;
    result = result * c % MOD;
    result = result * INV6 % MOD;
    cout << result << endl;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Số lượng hình vuông trong lưới N x N là tổng số hình vuông của tất cả các kích thước. Kích thước k (từ 1 đến N) có (N - k + 1)^2 vị trí. Tổng số hình vuông là sum{k=1}^{N} (N - k + 1)^2 = sum{i=1}^{N} i^2 = N(N+1)(2N+1)/6. Do N có thể lên đến 10^9, ta không thể tính vòng lặp. Ta cần tính công thức này trực tiếp. Để chia lấy dư cho số không nguyên tố (MOD = 10^9 + 7, là số nguyên tố), ta cần nhân với số modular inverse của 6 modulo MOD. Số inverse này là 166666668. Ta tính (N * (N+1) * (2N+1) * inv6) % MOD.

Cách Phương pháp chia thừa số (Factorization)

#include <bits/stdc++.h>
using namespace std;
const int MOD=1E9+7;
int main(){
    int n;
    cin>>n;
    int a= n;
    int b= n+1;
    int c= 2*n+1;
    if (a%2==0) a/=2;
    else if (b%2==0) b/=2;
    else if (c%2==0) c/=2;
    if (a%3==0) a/=3;
    else if (b%3==0) b/=3;
    else if (c%3==0) c/=3;
    long long s= 1ll*(1ll*a*b%MOD)*c%MOD;
    cout<<s;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Thay vì dùng số inverse, ta có thể chia trực tiếp các thừa số 2 và 3 ra khỏi tích N(N+1)(2N+1) trước khi thực hiện phép nhân modulo. Trong 3 số liên tiếp N, N+1, 2N+1, chắc chắn có số chia hết cho 2 và số chia hết cho 3. Ta kiểm tra từng số để chia cho 2 và 3. Sau khi loại bỏ thừa số 6, ta thực hiện phép nhân lấy dư với MOD. Cách này tránh dùng số inverse nhưng code phức tạp hơn một chút.

Cách Vòng lặp (Brute Force)

long long ans = 0;
for (int k = 1; k <= n; k++) {
    ans += (long long)(n - k + 1) * (n - k + 1);
}
ans %= MOD;

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất: duyệt qua từng kích thước k từ 1 đến N, tính số lượng hình vuông có kích thước k là (N-k+1)^2 và cộng dồn lại. Tuy nhiên, do N có thể lên tới 10^9, độ phức tạp O(N) của vòng lặp sẽ gây ra thời gian chạy quá giới hạn (Time Limit Exceeded). Phương pháp này chỉ khả thi với N nhỏ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về công thức tổng quát: Tổng bình phương các số từ 1 đến N là N(N+1)(2N+1)/6.
• Vì N rất lớn, ta phải dùng công thức trực tiếp thay vì vòng lặp.
• Khi chia lấy dư với số modulus là số nguyên tố (10^9+7), ta có thể dùng số modular inverse của mẫu số (6) hoặc chia thừa số trước khi nhân.

Lỗi thường gặp

• Sử dụng vòng lặp O(N)导致 Timeout với N lớn.
• Sai lệch khi chia lấy dư với số không chia hết (ví dụ chia 6 trực tiếp trong phép tính modulo). Cần dùng số inverse.
• Lỗi tràn số (Integer Overflow) khi tính toán nếu không sử dụng đúng kiểu dữ liệu (ví dụ dùng int thay vì long long cho các phép nhân).