统计方形（数据加强版）

题意

给定一个 n x m 的方格棋盘，统计其中包含多少个正方形，以及多少个长方形。这里“长方形”不包含正方形。

思路

先统计正方形。

如果正方形边长为 side，它的左上角有：

text

1(n - side + 1) * (m - side + 1)

种放法。枚举 1..min(n,m) 的所有边长并求和，就是正方形总数。

再统计所有矩形。一个矩形由两条横向网格线和两条纵向网格线决定：

text

1
2C(n + 1, 2) * C(m + 1, 2)
= n * (n + 1) * m * (m + 1) // 4

所有矩形数量减去正方形数量，就是题目要求的非正方形长方形数量。

Python 知识

Python 的 int 是任意精度整数，不用担心这里的计数超过 C++ int。
// 是整数除法，适合写组合计数公式。
range(1, min(n, m) + 1) 用来枚举所有可能的正方形边长。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10n, m = map(int, input().split())

square_count = 0
for side in range(1, min(n, m) + 1):
    square_count += (n - side + 1) * (m - side + 1)

all_rectangles = n * (n + 1) * m * (m + 1) // 4
rectangle_count = all_rectangles - square_count

print(square_count, rectangle_count)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m;

int main() {
    cin >> n >> m;
    ll sq = 0;
    for (ll side = 1; side <= min(n, m); side++)
        sq += (n - side + 1) * (m - side + 1);
    ll all = n * (n + 1) * m * (m + 1) / 4;
    ll rect = all - sq;
    cout << sq << " " << rect << endl;
    return 0;
}

Pythonic 写法

sum 推导数正方形：

python

1
2
3n, m = map(int, input().split())
squares = sum((n - s + 1) * (m - s + 1) for s in range(1, min(n, m) + 1))
print(squares, n * (n + 1) * m * (m + 1) // 4 - squares)

复杂度

时间复杂度为 $O(\min(n,m))$ ，空间复杂度为 $O(1)$ 。

总结

方格计数题要优先想“选边界”。所有矩形用选两条横线和两条竖线统计，正方形再按边长单独统计。

统计方形（数据加强版）

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结