CF453A Little Pony and Expected Maximum 题解
题目链接: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;
}
参考文献: