P2241 统计方形（数据加强版） 题解

WZWZWZWY · 2024-02-23 12:14:17 · 题解

怎么题解都是清一色的 O(nm)，有没有更新鲜的做法呢？

当然有，接下来请体验 O(n^2m^2) 到 O(1) 的极限优化吧……

一开始在讨论区浏览到一个帖子：

因为直接求长方形比较困难，所以可以通过求正方形个数和矩形个数来求长方形个数。我回复道：

大多数题解局限于此。可是真的只能优化到 O(nm) 吗？

（O(nm) 做法可以先参考上面的图片或其他题解，这里就不细讲了。）

先讲 O(\min(n+m))，为了比较透彻，所以篇幅相对来说有点大，请耐心QwQ。

建议大家拿出一张纸画画，如果你想象力强大，可以想象。

可以先想象出一个 4\times 6 的长方形框。

 ___________
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|_|_|

假设我们现在要求边长为 2 的正方形。先把左上角 2\times 2 的区域用正方形框起来。正方形最右边的格子的横坐标（从左往右数）是 2，最下边的格子纵坐标（从上往下数）也是 2，没问题吧？至于外圈的长方形，右下角的格子横、纵坐标分别是 4、6。

接下来这个正方形还可以往右移动小于等于 m-j 个格子（6-2=4），往下移动小于等于 n-i 个格子（4-2=2）。（假设不能向左和向上移动。）

所以这个正方形总共能存在的方案数为 (n-i+1)\times (m-j+1)。

为什么有个 +1 呢？因为可以某个方向不移动。每个方向的可能结果相乘就是存在的方案数。

知道了一个大小的正方形能出现多少次，就可以知道每个大小的正方形出现多少次。

因为正方形最大边长为 \min(n,m)，所以只要一个 for 循环依次枚举就能找到所有正方形的个数。

int k = min (n, m), cnt_zheng = 0; // 找正方形
for (int i = 1; i <= k; i++) {
    cnt_zheng += (n - i + 1) * (m - i + 1);
}

然后对于每个坐标 (i,j)，右面（包括正方形自己的最右边的那个格子）的格子个数（即横着的边的数量）乘以下面格子个数，就等于总共能形成的矩形个数（包括正方形和长方形）。

int cnt = 0;
for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) cnt += (n - i + 1) * (m - j + 1);

相减就是长方形个数。

但是，时间复杂度有点高。

我们把它拆开看看。（为了便于初学者理解，就不用 \sum 表示了。）

第二个循环内，n-i+1 似乎并不受影响，把它设为 x。变成了：

for (int i = 1; i <= n; i++) {
    int x = n - i + 1;
    for (int j = 1; j <= m; j++) cnt += x * (m - j + 1);
}

把第二层循环展开，可以表示为 x\times m + x\times (m-1)+\dots+x\times1=x(m+(m-1)+\dots+1)。

是不是有点眼熟？这不就是 x 倍的 m 到 1 的和吗？

一年级知识，等差数列求和公式：首项加尾项乘项数除以 2。

所以结果为 \frac{x(1+m)m}{2}，没问题吧？

成功地去掉了一个 for。

for (int i = 1; i <= n; i++) {
    int x = n - i + 1;
    cnt += x * (1 + m) * m / 2;
}

现在总的时间复杂度为 O(\min(n,m)+n)。

欸，我们又发现，这个 x 是不是也有规律？

我们依次把 i 带入，发现 x 是从 n 到 1。

因为 cnt=(x_1+x_2+\dots+x_n)\times \frac{(1+m)m}{2}。

而 x_{1\dots n} 又依次是从 n 到 1 中每个数。

也就是说 x_1+x_2+\dots+x_n=n+(n-1)+\dots+1=\frac{(1+n)n}{2}。

带回去，cnt=\frac{(1+n)n}{2}\times \frac{(1+m)m}{2}=\frac{(1+n)(1+m)nm}{4}。

所以我们可以 O(1) 地求矩形的总个数了！

cnt = (1 + n) * n * (1 + m) * m / 4; // 求矩形总个数

但我们求正方形的个数 O(\min(n,m)) 的时间复杂度，所以总的时间复杂度只能做到 O(\min(n,m))。

#include <iostream>
#define int long long
using namespace std;
signed main() {
    int n, m;
    cin >> n >> m;
    int k = min (n, m), cnt_zheng = 0;
    for (int i = 1; i <= k; i++) 
        cnt_zheng += (n - i + 1) * (m - i + 1);
    cout << cnt_zheng << " " << (1 + n) * n * (1 + m) * m / 4 - cnt_zheng;
}

但，仅限于此吗？

把求正方形的循环给展开。