P8692 [蓝桥杯 2019 国 C] 数正方形：结论，组合数学
题目描述
在一个 N×NN×N 的点阵上，取其中 44 个点恰好组成一个正方形的 44 个顶点，一共有多少种不同的取法？
由于结果可能非常大，你只需要输出模 109+7109+7 的余数。
如上图所示的正方形都是合法的。
输入格式
输入包含一个整数 NN。
输出格式
输出一个整数代表答案。
输入输出样例
输入 #1复制
4
输出 #1复制
20
说明/提示
对于所有评测用例，2≤N≤1062≤N≤106。
蓝桥杯 2019 年国赛 C 组 G 题
做法
正方形的放置分为正放和斜放。
先讨论正放情况。假设我们正放的正方形边长为i，那么我们我们在n*n的正方形中有（n-i）*（n-i)种放置方式。（有n-i行和n-i列要选）。
再讨论斜放情况。有一个结论：i*i的正方形中有i-1个最大内接斜正方形。我们1到n中的正方形有（n-i）*(n-i）个，那么斜放的就有（i-1）*（n-i）*(n-i)个。一共有i*(n-i)*(n-i)个
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n;
void solved(){
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){//正方形的边长
ans=(ans+i*(n-i)%mod*(n-i)%mod)%mod;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin>>t;
while(t--){
solved();
}
}