自动搬运

查看原文

来自洛谷，原作者为

	Furina_Hate_Comma > 最后在线时间：2025年8月24日0时8分 < 由 exOIso 发送激光

搬运于2025-08-24 22:41:30，当前版本为作者最后更新于2023-03-31 21:52:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道数学题。

我们分开处理在一个边长为 $i$ 的大正方体的情况 $(1\le i\le n)$。

只考虑目标正方形的顶点落在当前正方形的边上的情况。

挂一张丑图：

这是当 $i=4$ 时的情况。

我们关注到周围剩余的三角形，不难发现，四个直角三角形的直角边之和为 $4\times i$，也就是正方形的周长。

由于四个三角形全等，所以每个三角形的直角边和为 $i$。

设两条直角边分别是 $a$ 与 $b$，有 $a+b=i$ 且 $0 \le a,b \le i$。

当 $a$ 或 $b$ 取 0 时，即是整个大正方形，所以 $a=0$ 与 $a=i$ 的情况相同。

所以当大正方形边长为 $i$ 时，共有 $i$ 种情况使正方形四个点落在大正方形的边上。

而边长为 $n$ 的正方形中有 $(n-i+1)^2$ 个边长为 $i$ 的正方形。

证明：

若点 $a_{x,y}$ 若为小正方形左上的顶点，那么有：

$\begin{cases} x+i\le n+1\\y+i\le n+1\end{cases}$

解得：

$\begin{cases} x\le n-i+1\\y\le n-i+1\end{cases}$

故有 $(n-i+1)^2$ 个边长为 $i$ 的正方形。

最后统计即可。

代码：

十年 OI 一场空，不开 long long 见祖宗！

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int n,ans=0;
	cin>>n;
	n--;//由于给的是点，使用我们要转化为段
	for(int i=1;i<=n;i++){
		ans=(ans+(n-i+1)*(n-i+1)*i)%1000000007;
	}
	cout<<ans;
	return 0;
}