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），不需要額外存儲空間。