NOI手拉手问题

问题描述：

n个人n双手，每一次选择两个空手让这两个空手拉起来，然后这两个手不再是空手。一个人有两只手，问最终所有手都拉起来构成环的个数的期望。PS：一个人的左手和右手也可以拉起来构成一个环。

例如：n为2时，期望为4/3，假设从第一个人的左手开始，他的左手和右手和第2个人的左手和右手拉起来的概率都为1/3，其中自己的左手和右手拉起来构成环数为2，其他为1，则期望为1/3*2+1/3*1+1/3*1

题解：

1+1/3+1/5+……1/(2n-1)

如果直接看公式很容易理解，每多一个人，就多了两只手，假设除了这个人以外其他人的期望都算出来了，假设期望为F(n)，那么对于这个人来说无非两种情况，要么和自己拉，要么和别人拉，和自己拉的概率为1/(2n-1)，和别人拉的概率为(2n-2)/(2n-1)。和自己拉的话很好理解，在之前的期望上加1就好了，和别人拉的话就可以把这两个人绑定起来当成一个人就好了，期望就是之前的期望。所以用公式的话就是F(n+1)=F(n)*(2n-2)/(2n-1)+(F(n)+1)*1/(2n-1),化简就得F(n+1)=F(n)+1/(2n-1)，递归得F(n)=1+1/3+1/5+……1/(2n-1)

根据调和级数推到公式：

#include<bits/stdc++.h>
using namespace std;
#define ld long double
const int maxn = 1e7+7;
ld a[maxn];
void init(){
    a[0] = 0;
    a[1]=1;
    for(int i = 2;i<maxn;i++){
        a[i]=a[i-1]+1.0/(2*i-1);
    }
}
int main(){
    //freopen("head.in","r",stdin);
    //freopen("head.out","w",stdout);
    long long tmp;
    init();
    cin>>tmp;
    if(tmp*1.0>=maxn)
        cout<<log(2*tmp-1) - log(((2*tmp-1)-1)/2)/ 2 + 0.57721566490153286060651209 / 2<<endl;
    else
        cout<<a[tmp]<<endl;
    return 0;
}