LuoguP5147题解

发表于

数学技巧+期望

题目描述

HKE最近编写了一个函数rand(l,r)，其中l,r为正整数且l≤r。这个函数会等概率返回区间[l,r]中任意一个正整数。然后，他又编写了一个函数：

1
2
3
4
int work(int x){
    if(x==1)return 0;
    else return work(rand(1,x))+1;
}

这段代码用pascal写起来就是：

1
2
3
4
5
function work(x:integer):integer;
begin
    if x=1 then exit(0);
    else exit(work(rand(1,x))+1);
end;

现在给定一个正整数n, 请问work(n)的返回值的期望值是多少？

期望的定义：假设work(n)返回的所有可能的值为$x_1, x_2, \dots x_k$, 它们出现的概率分别为$p_1, p_2, \dots p_k$,则期望为：

$$E = \sum_{i=1}^k x_ip_i$$

Inputs & Outputs’ examples

Inputs’ e.g. #1

1
100000

Outputs’ e.g. #1

1
13.09014

分析

其实期望的计算公式题目里已经给了,就是:

$$E(n) = 0 \quad n = 1$$

$$E(n) = 1 + \frac 1n \sum_{i=1}^n E(i) \quad n > 1$$

那么考虑把第二个式子$\Sigma$前的系数消掉:

$$nE(n) = n + \sum_{i=1}^n E(i)$$

然后把$n-1$带入式子,可得:

$$(n-1)E(n-1) = (n-1)+\sum_{i=1}^{n-1} E(i) \quad \quad n>2$$

然后上下两式相减可得:

$$nE(n) - (n-1)E(n-1) = 1 + E(n)$$

化简可得:

$$E(n) = E(n-1) + \frac {1}{n-1}$$

右边式子的分式部分为调和计数,考虑在$n < 10^7$时暴力计算,否则直接$\ln(n)+\gamma$即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int LIMIT = 1e7 + 10;
const double _gamma = 0.5772156649015328;
double ans;
int n;
/* functions */
int main(int argc,char *argv[]){
	scanf("%d", &n);
	if(n == 1) {printf("%.5lf", 0.0); return 0;}
	if(n <= LIMIT) 
		FOR(i,1,n-1,1) ans += 1.0 / i;
	else ans = std::log(n) + _gamma;
	printf("%.5lf", ans + 1);
	return 0;
}

THE END