【调和级数】计蒜客31431 手拉手

题面在这里

​

考虑新加入第i个人，要么自己成环，要么加入某个已有的环内

而只有自己成环才对答案有1的贡献，概率为\(\frac 1 {2i-1}\)

答案就是：\(\sum_{i=1}^n \frac 1 {2i-1}\)

而\(\sum_{i=1}^n \frac 1 i\approx \ln n+c\)，\(c\)是欧拉常数

答案就是两个调和级数相减

​

示例程序：

#include<cstdio>
#include<cmath>
typedef long long ll;

const double C=0.57721566490153286060651209;
ll n;
int main(){
	freopen("hand.in","r",stdin);
	freopen("hand.out","w",stdout);
	scanf("%lld",&n);
	if (n<=1000000){
		double ans=0;
		for (int i=1;i<=n;i++) ans+=1.0/(2*i-1);
		printf("%.9lf",ans);
	}else{
		printf("%.9lf",(log(n)+C)/2+log(2));
	}
	return 0;
}