题解：UVA11971 多边形 Polygon

题解：UVA11971 多边形 Polygon

终于遇到一个数学题啦！

1. 大致题意

每组数据给你一个 n 和 k，求将一个长度为 n 的直线段，将其分切任意的 k 刀，即分成 k+1 个部分，求这 k+1 个线段能围成一个凸 k+1 边形的概率。

2. 解题思路

首先要确定的是，这是一道概率题，跟 n 无关。其次我们需要确定这 k+1 条必须满足什么条件才能满足可以围成一个凸 k+1 边形。

要确定 k+1 条直线段的长度应满足什么条件才能围成一个凸 k+1 边形，我们需要考虑多边形的边长条件。对于一个凸 k+1 边形，其边长必须满足以下条件：

1. 正长度：每条直线段的长度必须是正数。
2. 三角不等式：对于任意三条边，任意两边之和必须大于第三边。这个条件确保了任意三条边可以形成一个三角形，从而保证了多边形的凸性。

对于一个凸 k+2 边形，我们可以将这个条件推广到任意 k+1 条边。具体来说，对于任意 k+1 条边，任意 k 条边的长度之和必须大于第 k+1 条边的长度。这个条件确保了任意 k+1 条边可以形成一个凸 k+1 边形。

总结一下以上的分析，我们可以得到如下的结论：

任意的 k 条边的长度之和必须大于第 k+1 条边的长度。

我们再稍作转化，就可以得到如下的结论

对于凸 k+1 边形，其中的任意一条边的长度都必须小于周长的一半。

确定好条件之后，我们需要去考虑如何计算概率了。考虑到正向计算很难，所以我们可以方向考虑，即考虑围不成凸 k+1 边形。

由于最多只有一条边大于等于周长的一半，不妨设这条最长的边在最左侧，则剩下的 k 条边都在右边的概率为 \frac{1}{2^k}。下证为何是 \frac{1}{2^k}。

对于每一条小于周长的一半的直线段，其全部在右二分之一的概率为 \frac{1}{2}。再根据乘法原理，对于 k 条小于周长的一半的直线段，它们都在右二分之一的概率就为 \frac{1}{2^k}。

而由于一共有 k+1 条直线段，每条线段都可以大于等于周长的一半，所以虑围不成凸 k+1 边形的概率应为 \frac{1}{2^k} \times (k+1)，即 \frac{k+1}{2^k}。

结合上面的分析，可以得到最终的概率为 \frac{2^k-k-1}{2^k}。

3. 代码实现

我提出一些注意事项：

• 最终答案需要约分成最简分数。
• 当 k \le 2 是，答案是 0/1，约分时容易 Runtime Error。
• 一定要开 long long，因为 k \le 50。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, k, cnt;
int pow(int a, int b) {
    int ans = 1;
    while (b--) ans *= a;
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> k; cnt++;
        if (k <= 1) { cout << "Case #" << cnt << ": 0/1\n"; continue; }
        int a = pow(2, k) - k - 1, b = pow(2, k);
        int gcd = __gcd(a, b);
        cout << "Case #" << cnt << ": " << a / gcd << "/" << b / gcd << "\n";
    }
    return 0;
}

AC 记录