首页 > 代码库 > Codeforces Round #259 (Div. 1)——Little Pony and Expected Maximum
Codeforces Round #259 (Div. 1)——Little Pony and Expected Maximum
题目连接
- 题意:
输入n、m,表示一个n面的色子(面上的值为1-n),投掷m次,求得到的最大值的期望(1?≤?m,?n?≤?105). - 分析:
假设当前得到的最大值是Max,那么对应的概率是:sigma(C(m,k) * ((1 / n) ^ k )*(((Max - 1) / n) ^ (m - k)) ),(1 <= k <= n);化简就可以得到:sigma(C(m,k) * ((1 / n) ^ k )*(((Max - 1) / n) ^ (m - k)) ) - ((Max - 1) / n) ^ m,(0 <= k <= n);前半部分由二项式可以得到Max ^ m,那么化简结果就是Max ^ m - (Max - 1) ^ m。最后再乘以Max就是期望了。Max可以采用枚举的方式
感叹一下,才发现pow函数和快速幂的效率是一样的。。
int main () { int n, m; while (~RII(n, m)) { double ans = 0; FE(Max, 1, n) { ans += Max * (pow((double)Max / n, m) - pow((Max - 1.0) / n, m)); } printf("%.10f\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。