题面

问题描述

小R所在的小镇有 $n$ 个村落，这 $n$ 个村落分布在一个圆周上，这些村落之间两两有直达的小路，小路可能相交，但不存在三条路交于一点。现在小R正好 放暑假了，每天都在村落间游荡。一天，他发现可以从一个非村落的点出发，在 不经过村落的情况下经过三条小路再回到这个点。于是他很好奇，一共有多少个 这样的回路呢？

输入格式

第一行一个正整数 $n$，含义如上。

输出格式

第一行一个正整数，表示回路的个数。

题解

考后才知道，这是一个红题的加强版0.0

这个红题求的是对角线交点个数，很容易发现任意两条对角线都可以形成一个交点。因此答案为$n \choose 4$。

而本题，如果思路正确了，那很容易发现任意六个点连出的三条对角线(1->4,2->5,3->6)，也能形成一个三角形。

因此，答案为$n \choose 6$。。。

总结

找规律也要找好方法，不要把简单的问题复杂化了（指真正地去连出所有边数三角形个数）。以及这种可能和组合相关的一定要打个组合的表出来对着数据看0.0