题解 P5377 【[THUPC2019]鸽鸽的分割】

Imagine · 2019-05-20 18:03:51 · 题解

将整幅图看作平面图，套用欧拉公式：F - E + V = 2 \Rightarrow F = E - V + 2。

其中：

• 顶点数 V = n + \binom{n}{4}。
• 边数 E = n + \binom{n}{2} + 2\binom{n}{4}。

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

注意到平面图包含无限面，而应该计算的是圆内的区域，因此答案应减 1。

故答案即为 1 + \binom{n}{2} + \binom{n}{4}。

时间复杂度 O(1)。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  while (cin >> n) {
    int binom2 = n * (n - 1) / 2;
    int binom4 = n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
    cout << (binom2 + binom4 + 1) << '\n';
  }
  return 0;
}