洛谷 - P2181 - 对角线 - 打表 - 组合数学
https://www.luogu.org/problemnew/show/P2181
对于某条对角线,除去从两端出发的对角线,其他的都与它有1个交点。
每个点有(n-3)条对角线,每条对角线和其余C(n-2,2)条对角线都有1个交点,共有n个点,重复计算交点再除以2,重复计算直线再除以2。
即n(n-3)/2条对角线,每条对角线和(n-2)(n-3)/2条对角线都有1个交点,重复计算交点再除以2。(错了,并非所有对角线都相交)
画图手数,按规律数的话,发现n=4,1个交点;n=5,5个交点=sum(1,2)+2sum(1,1);n=6,15个交点=sum(1,3)+2sum(1,2)+3sum(1,1);n=7,35个交点=sum(1,4)+2sum(1,3)+3sum(1,2)+4sum(1,1)。
所以我们首先得到一个n复杂度的解法。利用这个解法打表看看。
#include<bits/stdc++.h>
using namespace std;
#define ll long long ll sum(ll a1,ll an){
return (an-a1+)*(a1+an)/;
} int main(){
for(int n=;n<=;n++){
ll ans=;
for(int i=;i<=n-;i++){
ans+=1ll*i*sum(,n--i);
}
printf("n=%d ans=%lld\n",n,ans);
} }
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
n= ans=
再试试大点的会不会爆,结果看不太出来,用ull和ll的结果没啥不同,赌他不溢出。
#include<bits/stdc++.h>
using namespace std;
#define ll long long unsigned ll sum(ll a1,ll an){
return (an-a1+)*(a1+an)/;
} int main(){
int n;
scanf("%d",&n);
//for(int n=99999;n<=100000;n++){
unsigned ll ans=;
for(int i=;i<=n-;i++){
ans+=1llu*i*sum(,n--i);
}
//printf("n=%d ans=%llu\n",n,ans);
printf("%llu\n",ans);
//} }
事实证明是没有溢出。所以上面是正确的解法。
这道题还有用公式的解法,降低了一个维度。除了用组合数学的知识直接得到(4个不同的点确定一个交点,直接C(n,4)),还可以暴力求解,这里介绍一下高阶差分。
首先我们由打表代码得到
35 70 126
一阶差分
二阶差分
三阶差分
四阶差分
五阶差分
所以上式是一个关于n的四次多项式。设为an^4+bn^3+cn^2+dn+e=0。
代入前5项强行算出来吧。还是说有别的计算方法?
的确有!(差分数列只要得到等差数列即可)
写出差分表之后,差分表的每行第0项组成第0对角线,即c0,c1,c2,c3,0,0,0...。原序列的通项满足
hn=c0C(n,0)+c1C(n,1)+c2C(n,2)+c3C(n,3),利用这个形式甚至可以求出前n项和。(组合数的求和sum(k=0~n,C(k,p))=C(k+1,p+1))
参考https://blog.csdn.net/wu_tongtong/article/details/79115921
最新文章
- 读书笔记--SQL必知必会14--组合查询
- 行为驱动开发iOS <;收藏>;
- 一些gcd计数问题
- 数据绑定控件之Repeater
- 用java实现文件下载,提示java.lang.IllegalStateException: getOutputStream() has already been called for this response
- 获取url的html值
- 使用复合索引代替单键索引,来避免单键有null值的情况
- JDBC学习笔记(1)
- Eclipse--Team--SVN--URL修改
- 分页加查询的sql语句
- Python 3语法小记(六)条件、循环和assert、pass、del
- [Git]Git远程仓库
- SPOJ QTREE 系列解题报告
- NDK下 将Platinum SDK 编译成so库 (android - upnp)
- vscode: Visual Studio Code 常用快捷键
- python之路第五篇之递归(进阶篇:续:经典例子剖析)
- 如何在Intellij IDEA中拉svn分支?
- Spring MVC Junit4 单元测试 JunitTest
- Object.clone()方法与对象的深浅拷贝
- 利用efi功能更改bios主板被隐藏的设置(如超频)