T749 localmaxima
原题：（权限限制没有超链接）
题目描述 Description
给出一个排列，若其中一个数比它前面的数都大，则称为localmaxima数，求一个随机排列中localmaxima数的个数的期望。
输入输出格式 Input/output
输入格式：
一个数n，表示排列为1-n的一个随机排列。
输出格式：
一个浮点数表示localmaxima数的个数期望。四舍五入保留8位小数。
输入输出样例 Sample input/output
样例测试点#1
输入样例：
2
输出样例：
1.50000000
说明 description
1,2的排列共两种：1,2和2,1.共3个localmaxima数。期望为3/2=1.5.
对30%数据n<=10.
对80%数据n<=1000000.
对100%数据n<=2^31-1
个人解法：
深深被数论的魅力所折服。
要非常非常感谢锟哥的帮助与学长的启发。
首先初看此题，全然没有思路。本来想是暴力table的了，但是很悲哀的是每一个n都会有全然不同的的答案，枚举？丝毫不可能成立……恐怕打表也只是等上几个小时的折腾了。
那么怎么办呢？
这个时候锟哥给了我启示。
既然我们是求期望嘛，就可以从每一个数开始入手。
这一题的数学期望就是
把每一个数成为localmaxima的情况加起来，再除以所有情况数。
至于所有的情况数，很简单，就是An取n，也就是n!。
于是我就开始着手于某一个数成为localmaxima的所有可能数。
先考虑了最简单的1。
1可能成为localmaxima的情况有多少种呢？
我们知道，在一个全排列中，没有比1小的。那么1只有放在第一位的时候可能成为localmaxima。那么这一共有多少种情况呢？很简单，就是A(n-1)取n-1，即(n-1)!。
那2呢？
我们发现，比2小的只有1。所以我们可以分两种情况：
第一种情况，2放在第一位，有(n-1)!种可能。
第二种情况，2放在第二位，因为2之前的数只可能是1才会让2成为localmaxima，所以有(n-2)!种可能。
如果2摆在第三位及以后，就必定会有一个比2大的数在2的前面，所以2就不再是localmaxima了，所以我们发现，对于一个数i，只需要考虑i放在第1至i位。
所以2成为localmaxima的可能一共有(n-1)!+(n-2)!种。
接下来考虑3。
比3小的有两个数，1和2。
那么我们就分三种情况讨论。
第一种情况，当然是3放在第一位，共(n-1)!种。
第二种情况，3放在第二位，这个时候比3小的有两个，1和2，所以就是(A2取1)*(n-2)!种。
第三种情况，3放在第三位，这个时候3之前的排列共有A2取2种，3之后的排列共有(n-3)!种，所以就是(A2取2)*(n-3)!种。
所以综合起来，就是(n-1)!+(A2取1)*(n-2)!+(A2取2)*(n-3)!。
诶，这个时候整理一下，我们就来规律了。
对于一个数i，它成为localmaxima的所有情况数应该是：
A(i-1取0)*(n-1)!+A(i-1取1)*(n-2)!+A(i-1取2)*(n-3)!+……+A(i-1取i-1)*(n-i)!
这个公式的意义是什么呢？就是考虑i在1至i的每一个位置j时，它前面的排列有A(j-1取i-1)种，后面的排列有A(n-j取n-j)种（也就是(n-j)!种）。所以就是1至i的累加和（那个符号不会打……）了。
于是我就试了几组数据。
首先是n，表示全排列的长度。
接下来n行。第i行的数表示i成为localmaxima的所有情况数：
n=5时
n=10时
n=20时
似乎并没有什么规律的样子。
后来想到要求的期望，每一个数变为local数的情况除以所有情况（n！）再加起来就是期望了。所以便想到把每一项求出来。
神奇的事就这样发生了。
我又试了几组数据。
首先是一个n，意义同上。
接下来n行。第i行的数字表示第i个数成为localmaxima的情况数除以n!（也就是全排列的总个数）的值。
n=5时
n=10时
n=20时
我想规律就显而易见了吧。
所以
ans=1/1+1/2+1/3+……+1/n
所以就这样把公式推导出来了。
接下来我就兴奋地把程序打了下来，本满以为可以AC，结果却发现测试点9和10都超时了，这个时候我才发现，n<=2^31-1。
那么怎么办？
这个时候就是学长给了我启发。
这个数学界都还没有解决彻底的问题呢……
对于大数据for的话是肯定超时了，不过我们还是可以肯定在80分的点用for还是可以过的，毕竟只有1000000。
那对于那么大的数嘛……
既然只需要精确到8为小数，我们就可以尝试一下调和级数了。
至于怎么用嘛……这里面很清楚https://baike.baidu.com/link?url=06w5WhIAzAi8FjOxV4WotFCikPRKmqMKAyGW-2wq-ToakcdLBxcl3XwNCvpBGaCwASC_5NQsV6gAEP-ncR9vTK
简单地说，就是1/1+1/2+1/3+1/4+……1/n=ln(n+1)+r，其中r是一个常数，好像叫欧拉常数吧。
很可惜的是，我们目前对于这个常数了解甚少……包括我们并不知道r到底是无理数还是有理数……
所以很明显了，对于前80分时不能用调和级数的，因为精度要求高，调和级数只是用于AC大数据的了（这在上面的论文中也有提及的样子）。
说了半天，代码只有13行，只是知识倒是精华了呢。
代码如下：
const
r=0.5772156649;
var
n,i:longint;
vk:double;
begin
read(n);
if n<=1000000 then//钱、前80分
for i:=1 to n do
vk:=vk+1/i
else vk:=ln(n+1)+r;//后20分
writeln(vk:0:8);
end.
再一次说，不得不被数论的魅力所折服。OI路上还有许多精彩与风景，希望与你们共同进步！