题解 CF453A 【Little Pony and Expected Maximum】

da32s1da · 2018-09-12 21:08:11 · 题解

一道期望DP

如果投n次，最大点数是k，那么情况共有k^n-(k-1)^n种。

若n次投掷的点数都在1到k内，共有k^n种情况。

若n次投掷的点数都在1到k-1内，共有(k-1)^n种情况。

这两个数值相减即可得到最大值是k的情况。

所以我们的期望ans=\frac{\sum_{i=1}^mi\times (i^n-(i-1)^n)}{m^n}=\sum_{i=1}^mi\times((\frac{i}{m})^n-(\frac{i-1}{m})^n).

#include<cstdio>
#include<cmath>
using namespace std;
double n,m,ans;
int main(){
    scanf("%lf%lf",&m,&n);
    for(double i=1;i<=m;i++)
    ans+=i*(pow(i/m,n)-pow((i-1)/m,n));
    printf("%.12lf\n",ans);
}