C++棋盘矩形个数计算：组合数学公式及代码实现

## 🧮 棋盘矩形个数计算 **核心思路**：在一个 N×M 的网格棋盘中，**任意一个矩形**可以由它的**两条水平边**和**两条垂直边**确定。 - 水平方向有 `N+1` 条线，从中任选 2 条作为矩形的上下边界 → 组合数 `C(N+1, 2)` - 垂直方向有 `M+1` 条线，从中任选 2 条作为矩形的左右边界 → 组合数 `C(M+1, 2)` - 总矩形数 = `C(N+1, 2) × C(M+1, 2)` = `N*(N+1)/2 * M*(M+1)/2` ### 📦 C++ 实现代码 ```cpp #include <iostream> using namespace std; int main() { long long N, M; // 使用 long long 防止溢出（N,M最大100时结果约为 2.5e7，但保险起见） cin >> N >> M; // 公式：N*(N+1)/2 * M*(M+1)/2 long long rectCount = (N * (N + 1) / 2) * (M * (M + 1) / 2); cout << rectCount << endl; return 0; } ``` ### 🔍 代码详解 - **`long long` 类型选择**：虽然 N,M ≤ 100 时结果最大约 `100*101/2 * 100*101/2 ≈ 25,502,500`，仍在 `int` 范围内（约 21 亿），但使用 `long long` 更安全，避免未来扩展或边界计算时的意外溢出。 - **公式推导**：`C(N+1, 2) = N*(N+1)/2`，同理垂直方向。两者相乘即为答案。 - **除法顺序**：先做乘法再除以2可能导致中间结果过大，因此**先除后乘**（`N*(N+1)/2` 保证整数除法），避免错误。 ### 📊 示例验证 | N | M | 矩形个数 | |---|----|----------| | 1 | 1 | 1 | | 2 | 2 | 9 | | 3 | 4 | 60 | | 5 | 5 | 225 | *验证*：2×2 棋盘有 9 个矩形（1个大 + 4个1×1 + 2个横2×1 + 2个竖1×2）。 ### 💡 替代方案讨论 1. **暴力枚举法**：`O(N² * M²)` 枚举所有左上/右下角点，复杂度高（N,M=100 时约 10^8 次运算，可能超时），不推荐。 2. **组合数学公式法**（本方案）：`O(1)` 时间复杂度，数学优美，推荐使用。 ### ⚠️ 常见陷阱与规避 - **数据类型溢出**：当 N,M 接近更大值（如 10^5）时，`int` 会溢出，务必用 `long long` 或 `__int128`。 - **除法的时机**：先乘后除可能导致无法整除，但此处 `N*(N+1)` 必为偶数，所以 `N*(N+1)/2` 安全。但推荐先除后乘以保证效率与正确性。 - **输入输出格式**：题目要求输出一行一个整数，注意换行符。 ### 🚀 扩展思考 - 若题目改为**正方形个数**，则公式变为：`Σ_{k=1}^{min(N,M)} (N-k+1)*(M-k+1)`。 - 若棋盘为 **N×M 的方格纸**，可以结合前缀和或循环优化递归问题。 ### 🧰 开发建议 - 使用 `long long` 处理计数类问题，**预防大数据量**。 - 写出清晰的注释，便于维护。 - 在本地测试边界条件：N=1, M=1 和 N=100, M=100。 ######[AI写代码神器 | 929点数解答 | 2026-08-28 20:42:44]