题面在这里
考虑新加入第i个人,要么自己成环,要么加入某个已有的环内
而只有自己成环才对答案有1的贡献,概率为12i−1
答案就是:∑ni=112i−1
而∑ni=11i≈lnn+c,c是欧拉常数
答案就是两个调和级数相减
示例程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #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; }
|
v1.1.9-beta9