牛客32282C-Little Pony and Expected Maximum

• 链接：https://ac.nowcoder.com/acm/contest/32282/C
• 知识点：概率期望、容斥
• 难度：绿

题意

• 一个骰子有 $mm$ 面，第 $ii$ 个面有 $ii$ 个点，每一面等概率出现，每次投掷的结果独立。
• 计算投掷 $nn$ 次骰子所能获得最大值的期望。

思路

• 一个骰子有 m 面，投掷 n 次，仅前 i 面出现的概率为 $(\frac{i}{m}{)}^n(\backslash frac\{i\}\{m\})^n$
• 所以答案 $ans=1\times (\frac{1}{m}{)}^n+2\times (\frac{2}{m}{)}^n+\mathrm{.}\mathrm{.}\mathrm{.}+n\times (\frac{n}{m}{)}^{n}ans=1\backslash times(\backslash frac\{1\}\{m\})^n+2\backslash times(\backslash frac\{2\}\{m\})^n+...+n\backslash times(\backslash frac\{n\}\{m\})^n$

上面这句话对吗？ 不对。 例如，$(\frac{2}{m}{)}^n(\backslash frac\{2\}\{m\})^n$ 的确是 仅前 2 面出现的概率，但是里面也包含了仅前 1 面出现的概率， 表达式中还将$(\frac{2}{m}{)}^n(\backslash frac\{2\}\{m\})^n$乘了 2，显然不合适，要先减掉 $(\frac{1}{m}{)}^n(\backslash frac\{1\}\{m\})^n$。

再例如，$(\frac{3}{m}{)}^n(\backslash frac\{3\}\{m\})^n$ 的确是 仅前 3 面出现的概率，但是里面也包含了仅前 1 面出现的概率和仅前 2 面出现的概率， 表达式中还将$(\frac{3}{m}{)}^n(\backslash frac\{3\}\{m\})^n$乘了 3，显然不合适，要先减掉 $(\frac{1}{m}{)}^n(\backslash frac\{1\}\{m\})^n$ 和 $(\frac{2}{m}{)}^n(\backslash frac\{2\}\{m\})^n$。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
const int N		= 1e6+10;
using namespace std;

int n, m;

void Solve()
{
	double ans = 0;
	double sum = 0;
	for (int i=1; i<=m; i++)
	{
		double tmp = pow(1.0*i/m,1.0*n);
		double p = tmp - sum;
		sum+=p;
		ans+=1.0*i*p;
	}
	printf("%.12lf\n",ans);
}

int main()
{
	scanf("%d %d",&m,&n);
	Solve();
	
	return 0;
}