[蓝桥杯 2019 国 C] 数正方形

[蓝桥杯 2019 国 C] 数正方形

题目描述

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

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

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

输入格式

输入包含一个整数 $N$。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

4

样例输出 #1

20

提示

对于所有评测用例，$2\le N\le 10^6$。

蓝桥杯 2019 年国赛 C 组 G 题

分析一：

对于N*N的正方形，它放置小正方形的情况为N

分析二：

我们下一步要求题目给的N*N正方形可以分成几个1×1,2×2,3×3

(n-i+1)(n-i+1)
n:正方形的边长

eg.对于3×3的正方形，求2×2的个数 ：（3-2+1）×（3-2+1）

分析三：

题目输入的N是点数，而不是边长
边长：N-1

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int k=1e9+7;
int ans=0;
signed main()
{cin>>n;n--;for(int i=1;i<=n;i++){int m=(n-i+1)*(n-i+1);ans=(ans+m*i)%k;}cout<<ans;return 0;
}