html 网站,腾讯做网站上传,自己做网站卖机器设备,wordpress 说明文档题目描述
在一个 NNNN 的点阵上#xff0c;取其中 44 个点恰好组成一个正方形的 44 个顶点#xff0c;一共有多少种不同的取法#xff1f;
由于结果可能非常大#xff0c;你只需要输出模 10971097 的余数。 如上图所示的正方形都是合法的。
输入格式
输入包含一个整数 …题目描述
在一个 N×NN×N 的点阵上取其中 44 个点恰好组成一个正方形的 44 个顶点一共有多少种不同的取法
由于结果可能非常大你只需要输出模 10971097 的余数。 如上图所示的正方形都是合法的。
输入格式
输入包含一个整数 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)个
#includebits/stdc.h
#define int long long
#define endl \n
using namespace std;
const int N1e510,mod1e97;
int n;
void solved(){cinn;int ans0;for(int i1;in;i){//正方形的边长 ans(ansi*(n-i)%mod*(n-i)%mod)%mod;}coutansendl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);int t1;//cint;while(t--){solved();}
}
