P2241题解

· · 题解

看题解里没有 O(1) 的算法，我来写一个 O(1) 的。

公式推导

（画的有些丑，请管理多多包涵一下 QAQ）

注：点数 = 边数 +\;1，n 为长方形的长，m 为长方形的宽。

长方形个数

我们可以这么想，长方形的长的起始点是 x，结束点是 y，宽的起始点是 a，结束点是 b（ x \ne y , a \ne b）。

也就是说，x,y 的选点方法总数是：

\begin{aligned} C^2_{n+1} &= \frac{A^2_{n+1}}{2!} \\ &= \frac{(n + 1) \times n}{2} \end{aligned}

同理，a,b 的选点方法总数是

\begin{aligned} C^2_{m+1} &= \frac{A^2_{m+1}}{2!} \\ &= \frac{(m + 1) \times m}{2} \end{aligned}

根据乘法原理，长方形个数（包括正方形为）：

\frac{(n + 1) \times n}{2} \times \frac{(m + 1) \times m}{2}

正方形个数

考虑每个正方形边长，直至边长为 m。

\cdots\cdots

总个数 =

\sum_{i = 0}^{m - 1} (n - i) \times (m - i)

该式子可化简为:

\frac{m \times (m + 1) \times[2 \times n + (n - m + 1)]}{6}

具体推导过程十分繁琐，具体推导过程请参考这里。

我们注意到，题目里所问的长方形不包括正方形，所以我们需要用长方形个数减去正方形个数。

代码：

#include <bits/stdc++.h>
using namespace std;
long long n,m;     //注意：这题需要开 long long
int main(){
    cin >> n >> m;
    if(n < m) swap(n,m);
    long long changfangxing = ((n) * (n + 1) / 2) * (m * (m + 1) / 2);
    long long zhengfangxing = (m) * (m + 1) * (2 * n + (n - m + 1)) / 6;
    cout << zhengfangxing << " " << changfangxing - zhengfangxing;
    return 0;
}