P2241 统计方形

发表于 分类于 阅读次数： Waline： 本文字数： 332 阅读时长 ≈ 1 分钟

考点

  • 枚举
  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ll n, m;
    cin >> n >> m;
    ll sum = ((n + 1) * n * (m + 1) * m) / 4;
    ll square = 0;
    for (int i = 1; i <= min(n, m); ++i)
        square += (n - i + 1) * (m - i + 1);
    cout << square << " " << sum - square;
    return 0;
}

思路

长方形的个数不好求，秉持着“正难则反”的原则，可以先求出一共有多少个矩形，再用矩形的数量减去正方形的数量即可

题意是说n*m个格子的棋盘，那么就有(n + 1) * (m + 1)个点

而矩形实际上就是行方向取两个点之间的长度作为宽，列方向取两个点之间的长度作为长；根据排列组合原理，有如下等式： \[ C_{n+1}^{2}\times C_{m+1}^{2}=\frac{\left( n+1 \right) !}{2!\times \left( n-1 \right) !}\times \frac{\left( m+1 \right) !}{2!\times \left( m-1 \right) !}=\frac{\left( n+1 \right) \times n\times \left( m+1 \right) \times m}{4}=\text{矩阵个数} \] 正方形的个数也很容易计算，边长为1的正方形个数+边长为2的正方形个数+...+边长为min(n, m)的正方形个数，也有如下等式 \[ \left( n-1+1 \right) \times \left( m-1+1 \right) +\left( n-2+1 \right) \times \left( m-2+1 \right) +...+\left( n-\min \left( n,m \right) +1 \right) \times \left( m-\min \left( n,m \right) +1 \right) \]