To solve this problem, we need to determine the number of rectangles (including squares) in an (m \times n) grid of squares.
Approach
The key insight here is that a rectangle is defined by choosing two distinct horizontal lines and two distinct vertical lines. Here's the breakdown:
- Horizontal Lines: An (m)-row grid has (m+1) horizontal lines (since each row is between two lines).
- Vertical Lines: An (n)-column grid has (n+1) vertical lines.
- Combinations: The number of ways to choose 2 horizontal lines from (m+1) is (\binom{m+1}{2}) (combination formula), and similarly for vertical lines it's (\binom{n+1}{2}).
- Total Rectangles: The product of these two combinations gives the total number of rectangles. The formula simplifies to: [ \text{Total Rectangles} = \frac{m(m+1)}{2} \times \frac{n(n+1)}{2} = \frac{m \times n \times (m+1) \times (n+1)}{4} ]
Solution Code
m, n = map(int, input().split())
result = (m * (m + 1) // 2) * (n * (n + 1) // 2)
print(result)
Explanation
- Combination Calculation: (\binom{m+1}{2}) is calculated as (m(m+1)/2) (since choosing 2 lines from (k) lines is (k(k-1)/2)).
- Product: Multiplying the combinations of horizontal and vertical lines gives the total number of rectangles, as each pair of horizontal lines combined with each pair of vertical lines forms a unique rectangle.
- Efficiency: The solution runs in (O(1)) time complexity since it involves basic arithmetic operations, making it extremely efficient even for large values of (m) and (n).
This approach correctly computes the number of rectangles in the grid using combinatorial mathematics, ensuring accuracy and optimal performance.


作者声明:本文包含人工智能生成内容。