棋盘正方形与长方形计数：C++数学公式实现及优化要点

## 🧮 棋盘正方形与长方形计数（C++） ### 📌 问题解析 对于 `N×M` 的棋盘，我们需要计算： - **正方形总数**：所有 `k×k`（`1 ≤ k ≤ min(N, M)`）的方格。 - **长方形总数**（不包括正方形）：所有 `a×b`（`a ≠ b`）的矩形。 --- ### 🧠 数学公式推导 #### 1️⃣ 正方形计数 对于边长 `k` 的正方形，在 `N` 行中可放置 `N - k + 1` 个，在 `M` 列中可放置 `M - k + 1` 个。 总正方形数： ``` S = Σ_{k=1}^{min(N,M)} (N - k + 1) * (M - k + 1) ``` #### 2️⃣ 长方形（含正方形）总数 所有矩形个数为：在 `N` 行中任选两行（含相邻的连续行），在 `M` 列中任选两列。 总矩形数： ``` R_total = [N*(N+1)/2] * [M*(M+1)/2] ``` （因为连续行段有 `N*(N+1)/2` 种选法，列同理） #### 3️⃣ 纯长方形（不含正方形） ``` R_pure = R_total - S ``` --- ### 💻 C++ 实现 ```cpp #include <iostream> using namespace std; int main() { int N, M; cin >> N >> M; // 计算正方形总数 long long squares = 0; int minDim = min(N, M); for (int k = 1; k <= minDim; ++k) { squares += (long long)(N - k + 1) * (M - k + 1); } // 计算所有矩形总数 long long totalRects = (long long)N * (N + 1) / 2 * (M * (M + 1) / 2); // 纯长方形 long long rectangles = totalRects - squares; cout << squares << " " << rectangles << endl; return 0; } ``` --- ### 🔍 关键点说明 | 知识点 | 解释 | |--------|------| | **数据类型** | 使用 `long long` 避免溢出。N、M 最大 100 时，总矩形数约 `(100×101/2)² ≈ 25,502,500`，仍在 int 范围内，但乘积中间值可能更大，保险起见用 long long。 | | **循环边界** | `min(N, M)` 确保边长不超过短边。 | | **公式选择** | 直接套用组合公式，时间复杂度 O(min(N,M))，远优于暴力枚举。 | --- ### ⚙️ 示例运行 输入： ``` 3 2 ``` 输出： ``` 8 10 ``` **验证**： - 正方形：1×1有6个，2×2有2个 → 共8个 - 总矩形：`(3×4/2) * (2×3/2) = 6*3 = 18`，纯长方形 = 18 - 8 = 10 ✅ --- ### 🚀 扩展优化建议 - **当 N、M 极大时**（如 10⁹），可考虑使用等差数列求和优化，但本题范围无需。 - **若需输出顺序**：题目要求先正方形后长方形，注意输出格式。 --- ### 🧩 常见陷阱 - **误将长方形公式套为 `C(N,2)*C(M,2)`** → 这是不连续的（选两行两列会漏掉连续段），必须用 `N*(N+1)/2`。 - **忘记减去正方形** → 导致长方形包含正方形。 --- ### 📚 延伸学习 - 组合计数基础：`[数学公式]` - 动态规划变体：若棋盘有障碍物，可改用 `[DP]` 逐格统计。 ######[AI写代码神器 | 919点数解答 | 2026-08-28 20:47:23]