【luogu2181】对角线
2024-10-09 09:59:49
首先由于不会有三条对角线交于一点,所以过某一个交点有且只能有2条对角线
而这两条对角线实质上是确定了4个顶点(也可以看做是一个四边形的两条对角线交于一点,求四边形的数量)。
因此我们只需要确定4个顶点就得到了这个唯一确定的交点。
因此我们只需要求这样4个顶点的搭配有多少个了
也就是从n个顶点中取4个出来。
根据组合数的公式,(如果你不知道组合数的公式可以这么推:第一次取可以n个点都是可以取的,第二次取的时候第一个取的点就不能取了,所以只能取(n-1)种,以此类推)
由于改变四个点的顺序不会改变对角线,因此是求的组合而不是排列,也就要除以4!,也就是24
于是我们就得到了公式: n (n-1) (n-2) * (n-3) / 24
同时为了防止爆掉,但又不想写高精,
我们可以采用一种化简的技巧
于是原式可以化为:
n (n-1) / 2 (n-2) / 3 * (n-3) / 4
那为什么这样一定是对的呢?难道不会因为除不尽却向下取整而导致错误吗?
事实上是一定除得尽的
首先n和n-1一定有一个是2的倍数,因此2可以除尽,
同理n,n-1,n-2中一定有一个是3的倍数,因此3可以除尽(除掉2只会消除因数2而对3没有影响)
同理4也可以除尽
完\(^o^)/~
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,ans;
int main()
{
scanf("%lld",&n);
ans=n * (n-) / * (n-) / * (n-) / ;
printf("%lld\n",ans);
return ;
}
最新文章
- XML基础
- 高性能缓存系统Redis安装与使用
- Hadoop的管理目录
- xcode添加音效
- java 超经漂亮验证码
- HTML字符实体
- 在VS 2010中使用 VS2013的解决方案
- java提高数据库访问效率代码优化
- 配置ADB 工具 (Win7_64)
- redis-2.6.16源码分析之pub-sub系统
- easyui combobox赋值
- Android模拟器设置竖屏
- Cookie中文乱码问题
- Windows下Nginx的配置及配置文件部分介绍
- OWA 无法连接到Exchange
- 关于如何登陆oracle 18c pdb 的问题
- 在Apache上http强制跳转到https
- ubuntu14静态ip配置
- m序列生成电路
- 8.30 牛客OI赛制测试赛1 F题 子序列