P5377 [THUPC2019] 鸽鸽的分割 题解
简要题意
连结圆上 \(n\) 个点,求最多能够把圆分成几个部分。
前置知识
欧拉公式:\(F(ace)=E(dge) - V(ertex)+2\)
人话:\(\text{多边形面数} = \text{边数} - \text{顶点数} + 2\)
思路
将一个圆折叠成一个多面体,你可以进行一些奇妙的空间变换来达到这一点。
那么我们最后会多出一个底面。
因此在我们的这个圆中 \(F(n)=E-V+1\)
求 \(V\)
圆上已经有了 \(n\) 个点。我们要使得圆内不存在三线共点的情况。
那么考虑每次选择四个顶点画出一个四边形的两条对角线。
于是又会生成 \(C_{n}^{4}\) 个顶点。可以证明已经考虑完全了,于是有
$$
V = n + C_{n}^{4}
$$
求 \(E\)
原有 \(C_{n}^{2}\) 条边,且圆环上的 \(n\) 个点互相连接构成 \(n\) 条边。
每多一个交点会增加两条多边形边。又有 \(2\times C_{n}^{4}\) 条。
$$
E = n + C_{n}^{2} + 2\times C_{n}^{4}
$$
最后,我们展开这个逆天的柿子:
$$
\begin{aligned}
F(n) &= E - V + 1 \\
&= n + C_{n}^{2} + 2\times C_{n}^{4} - n - C_{n}^{4} + 1 \\
&= C_{n}^{2} + C_{n}^{4} + 1 \\
&= \dfrac{n(n - 1)}{2} + \dfrac{n(n - 1)(n - 2)(n - 3)}{4\times 3 \times 2} + 1 \\
&= \dfrac{x^4}{24} - \dfrac{x^3}{4} + \dfrac{23x^2}{24} - \dfrac{3x}{4} + 1
\end{aligned}
$$
去 OEIS 上校验结果,正确。