P5377 [THUPC 2019] 鸽鸽的分割

题目描述

牛牛有一块蛋糕，他想把蛋糕分给小朋友们。蛋糕一开始是圆形的，牛牛会在圆周上选择 $n$ 个不重合的点，将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。

现在，牛牛想知道，蛋糕最多会被分成多少块，请你告诉他答案。

输入包含至多 $20$ 行，每行一个整数 $n$ ，含义见「题目描述」。保证 $0 \leq n \leq 64$ 。

依次回答牛牛的每个问题，对于每个问题，输出一行，包含一个整数表示答案。

1
2
3

2
3
4

1
2
3

2
4
8

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

拓扑学中的欧拉公式描述了凸多面体（convex polyhedron）的顶点（V）、边（E）和面（F）之间的基本关系：

F - E + V = 2

其中 $F$ 是面数， $E$ 是边数， $V$ 是边的交点数。可用数学归纳法证明这一公式。

本题中：

顶点数 $V (n) = n + (\binom{n}{4})$ 。
- $n$ ：圆上原本的点的数量。
- $(\binom{n}{4})$ ：任意四个点形成的两条线段均会产生一个交点。
边数 $E (n) = n + (\binom{n}{2}) + 2 (\binom{n}{4})$ 。
- $n$ ：圆上原本的 $n$ 个点将圆分成了 $n$ 条弧。
- $(\binom{n}{2}) + 2 (\binom{n}{4})$ ：每两个点之间存在一条线段。每一个交点会将相交的两条线段分成四部分，即增加两条线段。

因此， $F (n) = n + (\binom{n}{2}) + 2 (\binom{n}{4}) - n - (\binom{n}{4}) + 2 = 2 + (\binom{n}{2}) + (\binom{n}{4})$ 。

注意到平面图包含无限面，而应该计算的是圆内的区域，因此答案为 $F (n) - 1$ 。