245. 2019年蓝桥杯国赛 - 数正方形（困难）- 递推

245. 数正方形（困难）

2019年蓝桥杯国赛 - 数正方形（困难）

标签：2019 国赛 递推

题目描述

在一个 $N$×$N$ 的点阵上，取其中 4 个点恰好组成一个正方形的 4 个顶点，一共有多少种不同的取法？

由于结果可能非常大，你只需要输出模 $109+7$ 的余数。

如上图所示的正方形都是合法的。

输入描述

输入包含一个整数 $N(2\le N\le 106)$。

输出描述

输出一个整数代表答案。

输入输出样例

示例：

输入

4

输出

20

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解决思路

这道题目要求我们在 $N\times N$ 的点阵中，找到所有可以构成正方形的 4 个点。正方形的四个顶点之间具有特殊的关系，它们必须满足以下条件：

1. 所有的边长度相等。
2. 每两个相邻的顶点之间的距离是相等的。

分析

首先，我们需要明确如何在一个点阵中找到正方形。可以通过以下两种方式构建正方形：

**平行于坐标轴的正方形：**这些正方形的边是水平或垂直的，容易计算。假设正方形的边长为 $i$，那么每一个边长为 $i$ 的正方形，可以从点阵中的任意一个点出发，计算正方形的起始点位置及数量。

**旋转后的正方形：**这种正方形的边不一定与坐标轴平行，但它们依然满足正方形的四个点和边长相等的条件。计算过程与平行于坐标轴的正方形类似。

对于每一个边长 $i$ 的正方形，其顶点距离 $i$ 的水平和垂直距离都可以通过计算确定。通过枚举所有可能的边长，我们可以求解出所有正方形的个数。

公式推导

由 2.1的图表 可推得，对于每一个边长为 $i$ 的正方形，假设其起始点坐标为 $(x,y)$，我们可以确定正方形的 4 个顶点位置。如果正方形的边长为 $i$，那么从某个点开始，所有合法的正方形的个数为：
$$(n-i{)}^2\times i$$
其中，$(n-i{)}^2$ 表示可以选择的起始点数量，$i$ 表示每个正方形的边长。

算法步骤

1. 初始化计数器 $cont$ 为 $0$。
2. 遍历所有可能的边长 $i$ 从 $1$ 到 $n-1$。
3. 对每个 $i$，计算该边长对应的正方形个数，并累加到 $cont$ 中。
4. 最后输出 $cont$ 对 $109+7$ 取模的结果。

代码实现

# 获取边长
n = int(input())
MOD = 10**9 + 7  # 结果取模的常数

cont = 0
# 遍历所有可能的边长 i
for i in range(1, n):
    # 计算边长为 i 的空间下，正方形的个数
    cont += (n - i) ** 2 * i

# 输出最终的结果，取模 10^9 + 7
print(cont % MOD)

复杂度分析

时间复杂度：$O(n)$，遍历所有边长 $i$ 从 $1$ 到 $n-1$。

空间复杂度：$O(1)$，使用的变量为常数个（n, MOD, cont, i），不需要额外存储空间。
杂度分析

时间复杂度：$O(n)$，遍历所有边长 $i$ 从 $1$ 到 $n-1$。

空间复杂度：$O(1)$，使用的变量为常数个（n, MOD, cont, i），不需要额外存储空间。