P8692题解

amaimaic · 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} 若为小正方形左上的顶点，那么有：

解得：

故有 (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;
}