【题解】localmaxima 数论

摘要:
#T749localmaximas权限限制没有超链接标题描述。描述给出了一个数组。如果其中一个数字大于前面的数字,则称为localmaximum数。找到随机数组中局部最大值的期望值。样本输入/输出样本测试点#1输入示例:2输出示例:1.500000000描述描述有两种排列方式1,2:1,2和2,1。总共有三个局部最大值。然后,只有当1位于第一位置时,它才可能成为局部最大值。第i行中的数字表示第i个数变成局部最大值的情况数除以n!

# 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,所以就是A^{1}_{2}*(n-2)!种。
第三种情况,3放在第三位,这个时候3之前的排列共有$A^{2}_{2}$种,3之后的排列共有$(n-3)!$种,所以就是$A^{2}_{2}*(n-3)!$种。
所以综合起来,就是$(n-1)!+A^{1}_{2}*(n-2)!+A^{2}_{2}*(n-3)!$。
诶,这个时候整理一下,我们就来规律了。
对于一个数i,它成为localmaxima的所有情况数应该是:
$A^{0}_{i-1}*(n-1)!+A^{1}_{i-1}*(n-2)!+A^{2}_{i-1}*(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时
【题解】localmaxima 数论第1张
n=10时
【题解】localmaxima 数论第2张
n=20时
【题解】localmaxima 数论第3张
似乎并没有什么规律的样子。
后来想到要求的期望,每一个数变为local数的情况除以所有情况(n!)再加起来就是期望了。所以便想到把每一项求出来。
神奇的事就这样发生了。
我又试了几组数据。
首先是一个n,意义同上。
接下来n行。第i行的数字表示第i个数成为localmaxima的情况数除以n!(也就是全排列的总个数)的值。
n=5时
【题解】localmaxima 数论第4张
n=10时
【题解】localmaxima 数论第5张
n=20时
【题解】localmaxima 数论第6张
我想规律就显而易见了吧。
所以
$ans=1/1+1/2+1/3+……+1/n$
所以就这样把公式推导出来了。
接下来我就兴奋地把程序打了下来,本满以为可以AC,结果却发现测试点9和10都超时了,这个时候我才发现,$n<=2^{31}-1$。
那么怎么办?
这个时候就是学长给了我启发。
这个数学界都还没有解决彻底的问题呢……
对于大数据for的话是肯定超时了,不过我们还是可以肯定在80分的点用for还是可以过的,毕竟只有1000000。
那对于那么大的数嘛……
既然只需要精确到8为小数,我们就可以尝试一下调和级数了。
至于怎么用嘛……这里面很清楚http://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行,只是知识倒是精华了呢。
代码如下:

#include<cstdio>
#include<cmath>
#include<iostream>
#define re register int
using namespace std;
const double r=0.5772156649;
int n,i;
double vk;
int main(){
    freopen("T749.in","r",stdin);
    freopen("T749.out","w",stdout);
    scanf("%d",&n);
    if(n<=1000000) for(double i=1;i<=n;++i) {
        vk=vk+1/i;
//        cout<<vk<<endl;
    }
    else vk=log(n+1)+r;
//    cout<<log(n+1)+r<<endl;
    printf("%0.8lf",vk);
    return 0;
}

原文地址:http://liaoy148.lofter.com/post/1da8a74e_a3d612e

免责声明:文章转载自《【题解】localmaxima 数论》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇浅析b站2021/7/13日晚服务崩溃问题AIR:使用 HTML + Javascript 开发桌面应用下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

mysql之排序查询

高级文章目录3:排序查询功能:1.按单个字段排序案例1:查询员工信息,要求工资从高到低排序2.为排序添加筛选条件案例1:部门编号˃=90的员工信息,按员工编号降序排序案例2:部门编号˃=90的人员信息,按输入时间排序。按表达式排序案例1:按年薪显示员工信息和年薪4按别名排序案例1按年薪升序查询员工信息5.按函数(长度)排序案例1查询员工姓名并按姓名长度减少...

Linux 安装.src.rpm源码包的方法

接下来是rpm安装过程。...

layui table 打印表格

例如,layui的表单打印方法是将表单的数据重新组合成新页面,但它只能打印当前页面的内容。仅仅说实话是不够的。我整个上午都找到了一些,并说他们自己换了,但他们并不满意。这没用。我只能打印当前页面的内容。我的想法是编写一个函数,传递显示的列和要打印的数据,然后直接打印。不要胡说八道。直接转到代码。...

dBFs和dBm

dBFs和dBmdBFs是用来表征数字域功率值的大小,一般情况下我们定义0dBFs为数字域满刻度功率值,即数字域中功率的最大值;因此看到的dBFs的值都是负的。...

GeoServer基础教程(一):环境搭建篇

到目前为止,GeoServer环境已经建立,下面的博客文章将继续让您熟悉GeoServer的界面和基本功能。...

Qt自定义Widget中设置滚动条

用代码自定义一个独立显示的Widget,要在里面画图,同时加上滚动条,滚动条:  printerYuLanPainter=newQPainter();test=newQScrollArea();printerYuLanWidget=newQWidget(test);printerYuLanWidget-˃setMaximumSize(720,1000);pr...