简单期望题目

题意翻译

翻译来自洛谷

暮暮刚刚在和她的朋友——AJ（苹果杰克）、FS（小蝶）、RD（云宝黛西）玩Ludo游戏。但是她马品没攒够总是输。回到城堡过后，她对游戏用的骰子产生了兴趣。

题目描述

这个骰子有M面：骰子的第一面有一个点，第二面有两个点，以此类推，第m面含有M点。暮暮确信的是，当掷骰子时，每一面都有1/m的可能性出现，并且每次投掷的概率都是都是独立的。请你帮助她计算掷N次骰子后每次得到的点数中最大值的期望。

输入输出格式

输入格式：

一行两个整数 m 和 n (1 ≤ m, n ≤ 10^5).

输出格式：

输出一行一个实数，与答案误差不大于10^-4

输入输出样例

输入 #1

1

6 1

输出 #1

1

3.500000000000

输入 #2

1

6 3

输出 #2

1

4.958333333333

输入 #3

1

2 2

输出 #3

1

1.750000000000

说明/提示

Consider the third test example. If you’ve made two tosses:

1. You can get 1 in the first toss, and 2 in the second. Maximum equals to 2.
2. You can get 1 in the first toss, and 1 in the second. Maximum equals to 1.
3. You can get 2 in the first toss, and 1 in the second. Maximum equals to 2.
4. You can get 2 in the first toss, and 2 in the second. Maximum equals to 2.

The probability of each outcome is 0.25, that is expectation equals to:

You can read about expectation using the following link: http://en.wikipedia.org/wiki/Expected_value

解析

代码里什么都有

期望的公式是

顺便把注释里的两个式子渲染一下：

代码实现

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

#include <cstdio>

typedef double db;

db fp(db a, int b) { db r = 1; while (b) { if (b & 1) r = r * a; a = a * a; b >>= 1; } return r; }

int n, m;
double ans;

/**
 *
 * 掷 n 次骰子，最大点数不超过 k 的方案数为 k^n
 * 掷 n 次骰子，最大点数不超过 k - 1 的方案数为 (k - 1)^n
 * 减一下就可以知道最大点数为 k 的方案数
 * 然后套一下期望的公式就可以知道
 * ans = {\sum_{i = 1}^{m} i \times [i^n - (i - 1)^n] \over m^n}
 * 整理一下得到
 * ans = \sum_{i = 1}^{m} i \times \big[\big({i \over m}\big)^n - \big({i - 1 \over m}\big)^n\big]
 *
 */

int main() {
    scanf("%d %d", &m, &n);
    double last = 0;
    for (int i = 1; i <= m; ++i) {
        db d = fp(((double) i * 1.0) / ((double) m * 1.0), n);
        ans = ans + ((double) i * 1.0) * (d - last);
        last = d;
    }
    printf("%0.12lf\n", ans);
    return 0;
}