题号:P2181

题名:对角线

题目:对于一个 nn 个顶点的凸多边形,它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如,6 边形

这道题本身不难,但要涉及到一个名为“组合数公式”的东西。说白了就是从n个顶点中提取4个出来。

所以我们有了公式1.0版本:

 n*(n-1)*(n-2)*(n-3)/24

但这个公式有点复杂,所以我们可以对它进行简化。下面是公式2.0版本:

n*(n-1)/2*(n-2)/3*(n-3)/4

有人看到后肯定会说这不是更复杂了吗?实际上你把2,3,4提取出来再乘起来就和公式1一模一样了。

有人绝对会说难道不会因为除不尽却向下取整而导致错误吗?

事实上是一定除得尽的首先n和n-1一定有一个是2的倍数,因此2可以除尽,同理n,n-1,n-2中一定有一个是3的倍数,因此3可以除尽(除掉2只会消除因数2而对3没有影响)同理4也可以除尽。

好了,AC在此:

#include<bits/stdc++.h>//直接引入万能头文件
using namespace std;
int main(){//程序入口
    unsigned long long n,sum;//最大的整型变量,如果还不够大就需要高精度了
    scanf("%lld",&n);//用scanf的形式输入,更快
    sum=n*(n-1)/2*(n-2)/3*(n-3)/4;//直接套用上面已经说过的公式2.0即可,1.0也行
    printf("%lld",y);//直接输出sum的值
    return 0;//一个完美的结束
}

简化可直接复制版:

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    cout<<n*(n-1)/2*(n-2)/3*(n-3)/4;
    return 0;
}