【CodeVS1056】圆内三角形统计

Description

为了更好地解决这个问题，我们来看几个例子。

首先我们定义N！=1*2*3*……*N。

再定义C（M，N）为从M个元素中无序取出N个的方法，P（M，N）为从M个元素中有序取出N个的方法。

这样的定义是什么意思呢?比如说从1,2,3,4共4个元素中中取出3个,有(1,2,3);(1,3,4);(2,3,4);(1,2,4)这样共4种,而这里是不考虑顺序的,所以C(4,3)=4,而如果对每一种方案考虑它的排列顺序的话,那结果将会不同,因为(1,2,3);(1,3,2);(2,1,3);(2,3,1);(3,1,2);(3,2,1)将被视为不同的方案,所以P(4,3)=6*4=24.

下面给出它们的计算公式:

P(M,N)=M!/(M-N)! C(M,N)=M!/((M-N)!*N!)

再来解决这个问题,你会觉得更轻松!

圆周上有N（N<=100）个点，用线段将它们彼此相连。这些线段中任意三条在圆内都没有公共交点，问这些线段能构成多少个顶点在圆内的三角形？

Input

输入：一行，为数值N。

Output

输出：一行，为所求的答案。

Sample Input

样例输入：6

Sample Output

样例输出：1

HINT

注意：只要你数据处理得当，结果与中间数值的范围一定在longint以内，请不要使用int64，因为这可能会引起系统误判！

题解

看了很长时间也没看出样例是怎么凑出来的。。。

先画个圆，在圆里画一个三角形，然后延长三条边，和圆有6个交点。

所以，我们可以推出有7个点的情况，从7个点中任意找出6个点，就是一个三角形。（组合）

继续往后推，就可以推出公式Cⁿ_{6（符号不会打）。}

我们知道 $C_k^n ={n choose k} = frac{P_k^n}{k!} = frac{n!}{k!(n-k)!}$

于是我们把这个公式n!/6!(n-6)!变形成1/6!*n!/(n-6)! 而n!/(n-6)!=(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*n

(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*n/1/2/3/4/5/6 就是最终的公式

所以看出。。。题目里的提示是有用的。。。

#include<iostream>
using namespace std;
long long n;
int main(){
    cin>>n;
    cout<<(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*n/1/2/3/4/5/6;
}

维基百科组合数学