P5377 [THUPC2019]鸽鸽的分割

发表于 2022-05-17 分类于 OI
本文字数： 686 阅读时长 ≈ 1 分钟

标签：组合数学数学

P5377 [THUPC2019]鸽鸽的分割

Solution I

用欧拉公式推导：

$F = E - V + 2$

每四个圆上的点会产生两条线段，一个交点，故 $V = n + (\binom{n}{4})$ 。

$n$ 个点将圆划分为 $n$ 段圆弧，每两个圆上的点产生一条线段，每四个圆上的点产生的交点将两条线段划分为 $4$ 部分，故 $E = n + (\binom{n}{2}) + 2 (\binom{n}{4})$

故 $F = 2 + (\binom{n}{2}) + (\binom{n}{4})$ 。

注意到圆外还有一个面，答案为 $F - 1$ 。

Solution II

考虑每增加一个点，下面的弓形被划为 $n - 1$ 个平面，上面每三个点形成的三角形被划为两个平面，即有：
$f_{i} = f_{i - 1} + (\binom{n - 1}{3}) + n - 1$
答案为 $1 + \frac{n (n - 1)}{2} + (\binom{n - 1}{4})$ 。

查看代码

#include <cstdio>
using namespace std;
int main ()
{
    int n;
    while (~scanf("%d", &n))
        printf("%d\n", 1 + n * (n - 1) / 2 + n * (n - 1) * (n - 2) * (n - 3) / 24);
    return 0;
}