Hướng dẫn cho Bài 3: Hình Chữ Nhật, Không Phải Hình Vuông! (THT B Hà Tĩnh 2026)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho một lưới ô vuông kích thước \(n \times m\). Một hình chữ nhật được gọi là đẹp nếu nó không phải là hình vuông. Hãy đếm số lượng hình chữ nhật đẹp trong lưới và in ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).
Phân tích
- Điều kiện: \(1 \le n, m \le 10^9\).
- Nhận xét quan trọng: Một hình vuông cũng là một hình chữ nhật. Do đó:
- Số hình chữ nhật đẹp = (Tổng số hình chữ nhật) - (Tổng số hình vuông).
- Vì \(n, m\) lên đến \(10^9\), ta không thể sử dụng các vòng lặp để đếm mà cần tìm công thức toán học tính trong \(O(1)\).
Cách làm đơn giản (Brute Force)
Ý tưởng
- Tổng số hình chữ nhật: Chọn 2 đường ngang trong \(n+1\) đường và 2 đường dọc trong \(m+1\) đường. Số cách chọn là \(C_{n+1}^2 \times C_{m+1}^2 = \frac{n(n+1)}{2} \times \frac{m(m+1)}{2}\).
- Tổng số hình vuông: Duyệt qua từng độ dài cạnh \(k\) từ \(1\) đến \(\min(n, m)\). Với mỗi cạnh \(k\), số hình vuông kích thước \(k \times k\) là \((n-k+1) \times (m-k+1)\).
Độ phức tạp
- Thời gian: \(O(\min(n, m))\) để tính tổng số hình vuông.
- Đánh giá: Phù hợp cho Subtask 1 và 2 (\(n, m \le 2000\)). Với \(n, m = 10^9\), cách này sẽ bị quá thời gian (TLE).
Code Brute Force
C++
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, m;
cin >> n >> m;
long long MOD = 1e9 + 7;
long long total_rects = ((n * (n + 1) / 2) % MOD) * ((m * (m + 1) / 2) % MOD) % MOD;
long long total_squares = 0;
long long p = min(n, m);
for (long long k = 1; k <= p; k++) {
total_squares = (total_squares + (n - k + 1) * (m - k + 1)) % MOD;
}
long long ans = (total_rects - total_squares + MOD) % MOD;
cout << ans << endl;
return 0;
}
Python
Python
n, m = map(int, input().split())
MOD = 10**9 + 7
total_rects = (n * (n + 1) // 2) * (m * (m + 1) // 2) % MOD
total_squares = 0
p = min(n, m)
for k in range(1, p + 1):
total_squares = (total_squares + (n - k + 1) * (m - k + 1)) % MOD
ans = (total_rects - total_squares + MOD) % MOD
print(ans)
Hướng giải quyết (Tối ưu)
Công thức tính tổng số hình vuông
Ta cần tính nhanh tổng: \(S = \sum_{k=1}^{p} (n-k+1)(m-k+1)\) với \(p = \min(n, m)\).
Đặt \(i = k-1\), khi đó \(k = i+1\). Khi \(k\) chạy từ \(1\) đến \(p\), \(i\) chạy từ \(0\) đến \(p-1\):
\[S = \sum_{i=0}^{p-1} (n-i)(m-i) = \sum_{i=0}^{p-1} (nm - (n+m)i + i^2)\]
\[S = nm \cdot p - (n+m) \sum_{i=0}^{p-1} i + \sum_{i=0}^{p-1} i^2\]
Sử dụng các công thức tổng dãy số:
- \(\sum_{i=0}^{p-1} i = \frac{(p-1)p}{2}\)
- \(\sum_{i=0}^{p-1} i^2 = \frac{(p-1)p(2p-1)}{6}\)
Thay vào ta có:
\[S = nm \cdot p - (n+m) \frac{p(p-1)}{2} + \frac{p(p-1)(2p-1)}{6}\]
Lưu ý về lập trình
- Vì kết quả cần chia dư cho \(10^9 + 7\), khi thực hiện phép chia cho 2 và 6, ta cần nhân với nghịch đảo modulo.
- Nghịch đảo modulo của 2 là \(500000004\).
- Nghịch đảo modulo của 6 là \(166666668\).
Độ phức tạp
- Thời gian: \(O(1)\) (hoặc \(O(\log MOD)\) nếu tính nghịch đảo modulo bằng lũy thừa).
- Bộ nhớ: \(O(1)\).
Code tham khảo
C++
C++
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2);
}
int main() {
long long n, m;
cin >> n >> m;
// Tổng số hình chữ nhật: (n*(n+1)/2) * (m*(m+1)/2)
long long n_mod = n % MOD;
long long m_mod = m % MOD;
long long inv2 = modInverse(2);
long long inv6 = modInverse(6);
long long total_rects = (n_mod * (n_mod + 1) % MOD * inv2 % MOD) *
(m_mod * (m_mod + 1) % MOD * inv2 % MOD) % MOD;
// Tổng số hình vuông: nm*p - (n+m)*p*(p-1)/2 + p*(p-1)*(2p-1)/6
long long p = min(n, m) % MOD;
long long p_minus_1 = (p - 1 + MOD) % MOD;
long long term1 = (n_mod * m_mod % MOD * p % MOD);
long long term2 = (n_mod + m_mod) % MOD * p % MOD * p_minus_1 % MOD * inv2 % MOD;
long long term3 = p * p_minus_1 % MOD * (2 * p - 1 + MOD) % MOD * inv6 % MOD;
long long total_squares = (term1 - term2 + MOD) % MOD;
total_squares = (total_squares + term3) % MOD;
long long ans = (total_rects - total_squares + MOD) % MOD;
cout << ans << endl;
return 0;
}
Python
Python
import sys
def solve():
n, m = map(int, sys.stdin.read().split())
MOD = 10**9 + 7
# Nghịch đảo modulo
inv2 = pow(2, MOD - 2, MOD)
inv6 = pow(6, MOD - 2, MOD)
n_mod = n % MOD
m_mod = m % MOD
# Tổng số hình chữ nhật
total_rects = (n_mod * (n_mod + 1) * inv2 % MOD) * (m_mod * (m_mod + 1) * inv2 % MOD) % MOD
# Tổng số hình vuông dùng công thức O(1)
p = min(n, m) % MOD
p_minus_1 = (p - 1) % MOD
term1 = n_mod * m_mod % MOD * p % MOD
term2 = (n_mod + m_mod) % MOD * p % MOD * p_minus_1 % MOD * inv2 % MOD
term3 = p * p_minus_1 % MOD * (2 * p - 1) % MOD * inv6 % MOD
total_squares = (term1 - term2 + term3) % MOD
ans = (total_rects - total_squares + MOD) % MOD
print(ans)
solve()
Bình luận