Codeforces Round #259 (Div. 2) C - Little Pony and Expected Maximum

时间:2023-03-09 03:49:17
Codeforces Round #259 (Div. 2)  C - Little Pony and Expected Maximum

题目链接

题意:一个m个面的骰子,抛掷n次,求这n次里最大值的期望是多少。(看样例就知道)

分析:

m个面抛n次的总的情况是m^n, 开始m==1时,只有一种

现在增加m = 2,  则这些情况是新增的那个的第一次的结果的后面最大的都是新增的,

之前的这些的分支也加上这个数,而且这个数是这一支里最大的,也就是说新增产生的结果

全都是m = 2的这个结果,所以用现在的总的情况减去之前的总的情况。

所以:

最大值是1: 1种
2: 2^n-1
3: 3^n-2^n
.....
m: m^n-(m-1)^n

然后根据求期望的公式乘起来,但是不能直接n次方,比如m^n会严重超出数据类型。

可以分解一下就行了。
所以最后的结果=sum((k/m)^n - ((k-1)/m)^n) (1<=k<=m)

 #include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std; int main()
{
int i;
double ans, n, m;
while(cin>>m>>n)
{
ans = pow(1.0/m, n); for(i = ; i <= m; i++)
ans += (pow(i/m, n)-pow((i-)/m, n))*i; printf("%.4lf\n", ans);
}
return ;
}