题解

思路1

“暴力出奇迹，骗分过样例”老OIer常跟我们这样说，那么一看数据范围：$1 \le N, M \le 100$，好么，这不 $O(n^4)$ 都行吗！ 那就暴力枚举，枚举什么情况能够不重不漏呢？ 那么方形由什么构成？四条线。 怎样的四条线？两横两竖。 那我们就枚举线的位置，判断长方形还是正方形，然后加到 $ans1, ans2$ 里。

#include <bits/stdc++.h>
using namespace std;
int N, M, ans1, ans2;
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) // 枚举第一条线
        for (int j = i + 1; j <= N; j++) // 为了防止重复枚举，要j = i + 1
            for (int k = 1; k <= M; k++) // 注意这里枚举M个和前面的j没有关系，别写成k = j + 1了。
                for (int l = k + 1; l <= M; l++) // 这里写什么？写 k + 1，因为和上面的k有关系。
                {
                    if (j - i == l - k) // 两个边长一样，为正方形
                        ans1++;
                    else
                        ans2++;
                }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

思路2

我不屑于暴力枚举如果数据范围提升为 $1 \le N, M \le 10^6$，你的暴力枚举就不香了吧~ 那么如何 $O(n)$ 解决呢？这里我们要用到两个公式：

$$(N - x + 1) * (M - x + 1)$$

$$C_{N}^{2} * C_{M}^{2}$$

第一个式子可以求解在 $N * M$ 网格下，边长为 $x$ 的正方形个数。 第二个式子可以求解在 $N * M$ 网格下所有正方形和长方形的个数。 其实他们的原理也非常简单： 第一个式子，我们可以通过观察得出： 可以发现，$(N - x + 1)$ 可以求出 $N$ 方向上有多少长度为 $x$ 的线段，$(M - x + 1)$ 同理，这样根据乘法原理，就可以计算出来有多少了。 我们发现，$x$ 的取值在 $1$ 到 $min(N, M)$ 之间。 第二个式子利用了组合数，求出四条线的可能性。 这里 $C_{n}^{2}$ 根据组合数的定义，可以理解为 $n * (n - 1) / 2$。这样第二个式子就可以转化为：$N * M * (N + 1) * (M + 1) / 4$。可是这包含了正方形。我们可以通过减去前面的结果得到。

#include <bits/stdc++.h>
using namespace std;
int N, M, ans1, ans2;
int main()
{
    scanf("%d%d", &N, &M);
	for (int x = 1; x <= min(N, M); x++) // 枚举x
    {
		ans1 += (N - x + 1) * (M - x + 1); // 利用式子1
	}
    ans2 = N * M * (N + 1) * (M + 1) / 4 - ans1; // 利用式子2
    printf("%d %d\n", ans1, ans2);
    return 0;
}

$AC$ $Code$ $1$

#include <bits/stdc++.h>
using namespace std;
int N, M, ans1, ans2;
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++)
    for (int j = i + 1; j <= N; j++)
    for (int k = 1; k <= M; k++)
    for (int l = k + 1; l <= M; l++)
    {
        if (j - i == l - k) ans1++;
        else ans2++;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

$AC$ $Code$ $2$

#include <bits/stdc++.h>
using namespace std;
int N, M, ans1, ans2;
int main()
{
    scanf("%d%d", &N, &M);
	for (int x = 1; x <= min(N, M); x++)
		ans1 += (N - x + 1) * (M - x + 1);
    ans2 = N * M * (N + 1) * (M + 1) / 4 - ans1;
    printf("%d %d\n", ans1, ans2);
    return 0;
}

最后个大家来个最易懂的: 题目说的好，m,n<100，~~常言“暴力出奇迹”，~~我立刻想到了：

枚举

怎么枚举呢，显然，我可以先枚举左上的点，再枚举右下的点，坐标一减，是不是正方形显而易见 号称全国~NO.1~易懂的代码：

#include<bits/stdc++.h>
using namespace std;
int m,n,z,c,i,j,k,l;    //z用来记正方形个数，c来记长方形
int main()
{
	cin>>m>>n;           //输入
	for(i=0;i<=m;i++)    //枚举
	for(j=0;j<=n;j++)    //枚举
	for(k=i+1;k<=m;k++)  //还是枚举
	for(l=j+1;l<=n;l++)  //仍然是枚举
	if(k-i==l-j)z++;     //是正方形
	else c++;            //是长方形
	cout<<z<<" "<<c;     //输出
}

#### ~最后不要脸的求个赞~

说说公式是怎么推导的吧

找规律:

正方形:

边长为1的正方形个数为n*m

边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）

边长为3的正方形为个数(n-2)*(m-2)

边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)

然后从边长为1到min（m，m）的正方形个数全部加起来；

长方形:(包括正方形，好像正方形属于长方形来着？)

长为1的长方形（包括正方形）有n个

长为2的长方形（包括正方形）有n-1个

长为n的长方形（包括正方形）有1个

长为1到n的长方形1+2+...+n个

同理 宽为1的长方形（包括正方形）有m个

宽为2的长方形（包括正方形）有m-1个

宽为m的长方形（包括正方形）有1个

宽为1-m的长方形1+2+...+m个

然后把它们乘起来，根据乘法原理，总数s2=((1+n)*(1+m)nm)/4;

题目要求的是“非正方形的长方形”，因此要减去s1;

#include <bits/stdc++.h>

using namespace std;

int n,m,s1,s2;

int main()

{

cin>>n>>m;

    s2=((m+1)*(n+1)*m*n)/4;

    for(;m>=1&&n>=1;m--,n--)

    s1+=m*n;

    cout<<s1<<" "<<s2-s1;

    return 0;

}

列位看官:万水千山总是情，点个小赞行不行,看在我题解写的这么详细，源代码也有，请按一下题解旁边的大拇指行不行😪`(>﹏<)′

#include<bits/stdc++.h> using namespace std; int main() { int m,n,sqr=0; cin>>n>>m; int q=m,w; m=min(n,m); n=max(n,q); q=m; w=n; while(q>0){ sqr+=q*n; q--; n--; } cout<<sqr<<' '<<((w+1)w/2)((m+1)*m/2)-sqr; return 0; }