【题解】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=

随便看看

eureka服务列表刷新设置

服务器:当我们启用服务使用者时,它将向服务注册中心发送一个rest请求,以获取上面注册的服务列表。出于性能原因,eureka服务器将维护一个只读缓存服务列表以返回到客户端。默认情况下,缓存列表将每30秒更新一次。如果关闭UseReadOnlyResponseCache,服务器:#将不会读取只读缓存服务列表,因为每30秒刷新一次很慢,所以读/写缓存过期策略Us...

IOS崩溃日志解析(crash log)

IOS的应用程序少不了crash,互联网统计分析工具友盟有一项目错误分析的功能,专门用于应用程序崩溃日志统计,最近研究友盟上统计到的崩溃日志,在此对崩溃日志做一个简单的总结。否则,应用将被iOS终止,并产生低内存崩溃报告。这样,我们去我们的dSYM文件看看我们的UUID是否和崩溃日志上的UUID一致,只有dSYM文件的UUID和崩溃日志上的UUID一致,我们...

mysql状态查看 QPS/TPS/缓存命中率查看

showglobalstatusslike'Com_ commit';showstatslike“无缓冲池读取%”;Thread_cache_Hits=(1-Thread_created/connections)*100%(8)锁定状态mysql&gt;showstatslike“Binlog_缓存%”;...

01 . 美团全链路监控CAT简介及部署

现任携程架构总监)领导基于Java开发的实时应用程序监控平台的设计。作为大众点评网的基本监控组件,AT为大众点评网业务线提供系统的性能指标、健康状态、基本警报等。如何有效定位故障并缩短故障。。。监控是运维工作中最重要的环节,吴启民也是开源实时监控系统CAT的作者。系统故障监控、业务指标监控、应用程序性能监控、用户行为监控、安全合规性监控等,如分布式监控系统C...

[笔记]manjaro kde主题&amp;amp;手动安装主题

安装manjaroKDE主题。首先,安装manjaro主题,有两种方法:“系统设置”-“全局主题”-“获取新的全局主题”,您还可以在“外观”中获得“等离子样式、应用程序样式、颜色等”的新全局主题“.通过manjarokdestore下载主题,然后将主题导入系统。但是,由于某些原因,方法1在我的计算机上不可行。加载速度非常慢,下载速度非常慢。据说可以通过pro...

antd Tabs组件动态加载组件内容

Tabs的TabPane子组件不支持将属性传递给Component,并且官方示例的TabPane内容仅为简单文本。...