Codeforces 453A《Little Pony and Expected Maximum》

简单期望题目

题意翻译

翻译来自洛谷

暮暮刚刚在和她的朋友——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:
$(2+1+2+2) \cdot 0.25=\frac{7}{4}$
You can read about expectation using the following link: http://en.wikipedia.org/wiki/Expected_value

解析

代码里什么都有

期望的公式是 $E(x) = \sum P(x = i) \times i$

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

代码实现

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;
}