UVa 11971 (概率) Polygon

时间:2022-02-19 21:29:00

题意:

有一根绳子,在上面随机选取k个切点,将其切成k+1段,求这些线段能够成k+1边形的概率。

分析:

要构成k+1边形,必须最长的线段小于其他k个线段之和才行。

紫书上给出了一种解法,但是感觉理解得不是太好,所以又去网上找了其他解法。

知乎上有人问过这个问题,而且给出了很多种严格的解法。

最后代码里将(1LL << i)写成(1 << i),这种细节应当注意。

 #include <cstdio>
typedef long long ll; ll gcd(ll a, ll b)
{
if(b == ) return a;
return gcd(b, a % b);
} const int maxn = ;
ll a[maxn + ], b[maxn + ]; void Init_table()
{
b[] = ;
for(int i = ; i <= maxn; ++i)
{
ll g;
b[i] = 1ll << i;
a[i] = b[i] - i - ;
g = gcd(a[i], b[i]);
a[i] /= g, b[i] /= g;
}
} int main()
{
Init_table();
int t;
scanf("%d", &t);
for(int kase = ; kase <= t; ++kase)
{
int k;
scanf("%d", &k);
scanf("%d", &k);
printf("Case #%d: %lld/%lld\n", kase, a[k], b[k]);
} return ;
}

代码君