额。。最为VIJOS回归之后做的第一题。还是蛮有意思的。。
传送门
首先可以看出答案是1到n的倒数和。。
有两个办法。。一个是我开始想到的就是设F(x)为1到x的排列的答案。
那么若这个排列第一个是1。那么就是F(x-1)+1否则在中间的1可以忽略掉，就是F(x-1)。。
那么F(x)=( F(x-1)+1 )/x +F(x-1)*(x-1)/x。。
就是F(x)=F(x-1)+1/x。。。
这个方法只有我这样菜的人才想的出来囧。。
一般来说第i个数为Local Maxima的概率就是他为前i个中最大的概率，就是1/i。。
然后+起来。。
不过数据范围太TMD大了。。
我一开始想是不是要用矩阵加速，感觉不是齐次的搞不出来。。。
最后wiki了一下调和数列，发现原来是有公式的。。
zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89-%E9%A9%AC%E6%AD%87%E7%BD%97%E5%B0%BC%E5%B8%B8%E6%95%B0
因为精度的问题，对于n<=10^6次方的时候。。暴力计算，
否则使用公式。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
const int limit=1e6;
int main()
{
int n;cin>>n;double ans=0;
if(n<=limit)
for(double i=1;i<=n;i++)
ans+=1/i;
else
ans=log((double)n)+0.57721566490153286060651209;
printf("%0.8lfn",ans);
}P.S我的vijos号由于注册的比较早。不叫WJMZBMR。。好像是453844077囧。。我在想是不是为了统一风格就不要原来的号了又舍不得100多道题目囧。。