【luogu U138098】超级蚯蚓（数学概率）
超级蚯蚓
题目链接：luogu U138098
题目大意
给你 n 个线段，你每次会随机选两个线段头合起来，问你和 n 次之后恰好变成一个大环的概率。
思路
我们考虑每成功的合成一次，线段的数量就会少 1 1 1。
那合成 n − 1 n-1 n−1 次（成功）之后，就变成只有一个线段，那只有两个头，无论怎么和都是成功的。
然后我们考虑求成功合成每一步的概率。
要把
i
i
i 个线段合成成
i
−
1
i-1
i−1 个，那有
2
i
2i
2i 个头可以选，我们考虑一下怎样选是不可以的。
那就是选一条线段的两个头，那这个线段就提前变成了环，这样的情况有
i
i
i 种，而所有的概率是
C
2
i
2
C_{2i}^2
C2i2，即
2
i
(
2
i
−
1
)
2
\dfrac{2i(2i-1)}{2}
22i(2i−1)。
减一下，成功的概率就是
2
i
(
2
i
−
1
)
2
−
i
2
i
(
2
i
−
1
)
2
\dfrac{\frac{2i(2i-1)}{2}-i}{\frac{2i(2i-1)}{2}}
22i(2i−1)22i(2i−1)−i。
当然你也可以化简：
=
2
i
(
2
i
−
1
)
−
2
i
2
2
i
(
2
i
−
1
)
2
=\dfrac{\frac{2i(2i-1)-2i}{2}}{\frac{2i(2i-1)}{2}}
=22i(2i−1)22i(2i−1)−2i
=
2
i
(
2
i
−
1
)
−
2
i
2
i
(
2
i
−
1
)
=\dfrac{2i(2i-1)-2i}{2i(2i-1)}
=2i(2i−1)2i(2i−1)−2i
=
2
i
(
2
i
−
2
)
2
i
(
2
i
−
1
)
=\dfrac{2i(2i-2)}{2i(2i-1)}
=2i(2i−1)2i(2i−2)
=
2
i
−
2
2
i
−
1
=\dfrac{2i-2}{2i-1}
=2i−12i−2
但其实化简不化简都无所谓。
然后你要每一步都成功，那就是每步成功的概率乘在一起就是答案了。
代码
#include<cstdio>
#define ll long long
using namespace std;
int n;
double f[1001];
int main() {
scanf("%d", &n);
f[1] = 1;
for (int i = 2; i <= n; i++) {
int di = (2 * i) * (2 * i - 1) / 2;
f[i] = 1.0 * (di - i) / di;
}
for (int i = 2; i <= n; i++)
f[i] *= f[i - 1];
printf("%.6lf", f[n]);
return 0;
}