UVA 11971 Polygon——连续概率

UVA 11971 Polygon——连续概率

一开始真没想到，紫书的做法很巧妙，首先确定本题的答案与n无关，然后把直线首尾相连形成一个圆，问题就转化成了在圆上随机选k+1个点。

现在考虑组不成多边形的概率，仔细想一想会发现当其中一个小木条至少跨越半个圆周时组不成多边形，所以我们针对这种情况求其概率，我们先选一个点i，点i与圆心连接起来的直线将圆划分成两部分，这两部分设为A 和 B，除了点i之外其余个点位于A的概率均为1/2，总概率为（1/2）^k,点i的取法有k+1种，因此组不成多边形的概率为（k+1）/2^k,答案就是1-（k+1）/2^k,然后用gcd约分一下就好了

#include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 100;ll dp[maxn];ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b);}int main() { dp[0] = 1; for (int i = 1; i <= 50; i++) dp[i] = dp[i-1]*2; int T, n, k; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &n, &k); int c = gcd(k+1, dp[k]); printf("Case #%d: %lld/%lld\n", kase, dp[k]/c-(k+1)/c, dp[k]/c); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。