洛谷 P2181对角线——排列组合

洛谷 P2181对角线——排列组合

P2181看到的时候觉得思考难度极大,想要利用图论求解,但没有思路,最后从答案中明白,核心是排列组合,三条对角线不会交于一点,所以任何一点都必须由两条对角线组成——即四个点确定一个交点

也就是问,顶点集中取4个点有几种取法?排列组合比较的明显了。

后续细节上还有大精度的问题,用long long也会爆掉,要用unsigned long long 并且可以把除法分解提前减少计算上限