【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个点，就是一个三角形。（组合）
继续往后推，就可以推出公式Cn6（符号不会打）。
我们知道
于是我们把这个公式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; }优质内容筛选与推荐>>
1、ASP.NET(C#)常用数据加密和解密方法2
2、如何实现LAN或WAN远程开机?
3、maven常见问题汇总 专题
4、【贪心】闭区间问题
5、PHP安装和配置