CF453A Little Pony and Expected Maximum 题解

题意：

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

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

输入格式：

一行两个整数 $m$ 和 $n (1 \le m, n \le 10^5)$ 。

输出格式：

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

扔 $n$ 次，最大值是 $k$ 的方案数有 $k^n - (k-1)^n$ 种，每种方案对答案的贡献是 $k$ 。

因此

$\begin{aligned} \mathrm{Ans} &= \frac{\sum_{i=1}^m i\times(i^n - (i-1)^n)}{m^n} \\[6pt] &= \sum_{i=1}^m i \times\left(\left(\frac{i}{m}\right)^n-\left(\frac{i-1}{m}\right)^n\right) \end{aligned}$

时间复杂度 $\mathcal{O}(m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n, m; double res;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> m >> n;
    for(double i = 1; i <= m; i++)
        res += i * (pow(i / m, n) - pow((i - 1) / m, n));
    cout << fixed << setprecision(12) << res << '\n';
    return 0;
}