棋盘正方形与长方形计数——C++组合数学实现

好的，我们来详细解决这个问题。这是一个经典的棋盘计数问题，核心是 **组合数学** 的应用。 ## 🧩 问题分析 在一个 \( N \times M \) 的网格中，我们需要分别计算： 1. **所有正方形的数量**（边长为1, 2, 3, ... 的正方形）。 2. **所有长方形的数量**（不包括正方形，即长宽不等的矩形）。 --- ## 🧮 核心数学公式 ### 📐 1. 所有矩形的总数（包括正方形） 在一个 \( N \times M \) 的网格中，任意一个矩形由 **两条水平线** 和 **两条垂直线** 确定。 - 水平方向有 \( N+1 \) 条线，选择2条：\( C(N+1, 2) \) - 垂直方向有 \( M+1 \) 条线，选择2条：\( C(M+1, 2) \) **所有矩形（包括正方形）的总数**为： \[ \text{total\_rectangles} = C(N+1, 2) \times C(M+1, 2) = \frac{N(N+1)}{2} \times \frac{M(M+1)}{2} \] ### 🔲 2. 所有正方形的数量 边长为 \( k \) 的正方形，在水平方向可以放置 \( (N - k + 1) \) 个，在垂直方向可以放置 \( (M - k + 1) \) 个。 所有正方形的总数为： \[ \text{squares} = \sum_{k=1}^{\min(N, M)} (N - k + 1) \times (M - k + 1) \] ### 🟦 3. 所有长方形（不含正方形）的数量 直接用 **所有矩形总数** 减去 **正方形总数** 即可： \[ \text{rectangles} = \text{total\_rectangles} - \text{squares} \] --- ## 💻 C++ 代码实现 ### 🚀 代码思路 1. 使用 `long long` 类型（或 `unsigned long long`）避免溢出，因为 \( N, M \) 最大为 100，但矩形数量可能达到 \( \frac{100 \times 101}{2} \times \frac{100 \times 101}{2} \approx 25,502,500 \)，适合用 64 位整数。 2. 按照公式计算。 ```cpp #include <iostream> #include <algorithm> // for std::min using namespace std; int main() { int N, M; // 假设输入格式为：N M （空格分隔） cin >> N >> M; // 使用 long long 防止乘法溢出 long long total_rectangles = (long long)N * (N + 1) / 2 * M * (M + 1) / 2; long long squares = 0; int limit = min(N, M); for (int k = 1; k <= limit; ++k) { squares += (long long)(N - k + 1) * (M - k + 1); } long long rectangles = total_rectangles - squares; // 输出结果，以逗号分隔，符合题意 cout << squares << "," << rectangles << endl; return 0; } ``` --- ## 📘 输入输出示例 **输入：** ``` 3 2 ``` **输出：** ``` 8,10 ``` --- ## ⚠️ 常见陷阱与优化建议 1. **整数溢出**： - 当 \( N, M \) 接近 100 时，`N*(N+1)/2 * M*(M+1)/2` 的结果可能超过 `int` 范围（约 21亿），必须使用 `long long`。 2. **输入格式**： - 题目给的示例用 **逗号** 分隔输入，但通用题目通常用 **空格**。建议在代码中做灵活处理，例如： ```cpp // 支持逗号或空格分隔 char comma; cin >> N >> comma >> M; // 如果输入是 "3,2" ``` 但为通用性，上述代码使用空格。根据实际题目要求调整。 3. **边界情况**： - 当 \( N = 1 \) 或 \( M = 1 \) 时，正方形数量 = 1×? 或 ?×1，公式依然正确。 - 当 \( N = 1, M = 1 \) 时，只有 1 个正方形，0 个长方形。 4. **时间复杂度**： - 我们的解法是 \( O(\min(N,M)) \)，对于 100 来说非常快。实际上也可以用公式直接计算正方形总数（平方和），但循环已足够，且更易读。 --- ## 🧑‍💻 开发建议 - **代码可读性**：使用有意义的变量名，如 `squares`、`rectangles`。 - **类型安全**：显式使用 `long long`，避免隐式转换导致精度丢失。 - **测试驱动**：多测试边界值（如 N=1, M=100）和对称输入（ N=M ）。 - **扩展性**：如果想同时输出所有矩形的长宽统计，可以改为二维数组或组合公式。 --- ######[AI写代码神器 | 1193点数解答 | 2026-06-06 07:46:30]