统计方形（数据加强版）

zhyyyyy115 / 2023-05-03 / 原文

统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 $n \times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 $n,m$（$n \leq 5000,m \leq 5000$）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

2 3

样例输出 #1

8 10

思路

题意：

矩形数 = 正方形数 + 长方形数
是 n * m 的方格棋盘而不是矩阵
注意数据范围 long long

示例：
长方形：
求 n * m 的格子内有多少，长为2，宽为1的长方形

正方形：

求n * m 的格子内有多少，长为2，宽为1的正方形

推论：

\[n*m矩形个数 \begin{cases} 长方形：(n-i)*(m-j) & \text {if $i != j$}\\ 正方形：(n-i)*(m-j) & \text {if $i == j$ } \end{cases} \]

题解

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6+5; 

int n, m;
ll a, b;

void solve() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i != j) {
                a += (n-i)*(m-j);
            } else {
                b += (n-i)*(m-j);
            }
        }
    }    
    cout << b << " " << a << "\n";
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 
    // cin >> t;
    // while(t--) {
        solve();
    // }
    return 0;
}