700题咯！！！！

不是很懂楼下的化简，直接f[i]=i*(i^n-(i-1)^n)/(m^n)直接算啊？

#include<stdio.h>
#include<math.h>
#define d double
int m,n; d ans=0.;
int main(){
    scanf("%d%d",&m,&n);
    for(int i=m;i;--i)
        ans+=i*(pow((d)i/m,n)-pow((i-1.)/m,n));
    printf("%.4lf\n",ans);
}

这题是算数学期望题目，关键是怎么算的快，不能越界，不能丢精度，关于精度问题好像不是特别重要，关键是不越界。

一共m朵花，第i朵有i片花瓣，i=1...m, 一共随机n次，每次选一朵花，问这n次选到的一朵花花瓣数最大值的期望是多少。

典型数学题，先列公式，E=sum(i=1..m) i*(i^n-(i-1)^n)/m^n, 直接计算出现指数，m n较大，显然不行，除非高精度，不过太费周折，
于是简化公式，把公式展开，带i的一坨变为 1*1^n-1*0^n+2*2^n-2*1^n+....m*m^n-m*(m-1)^n=m*m^n-(1^n+...(m-1)^n)/m^n, 当时
还一直在想有没有1^n+..m^n的求和公式，结果发现特别复杂，看来不对，不过一看这个，已经可以计算了，因为每一项都可以除以分母了，是小数的指数次
于是直接列公式搞定。

代码如下：

int main()
{
int m, n;
while(cin>>m>>n)
{
double sum=m;
for(int i=1;i<m;i++)
{
sum-=pow(double(i)/m, n);
}
printf("%.4f\n", sum);
}
return 0;
}

这里面有一点组合数学的技巧，或者说对立事件，例如选择最大为i的次数，用1...i里面选n次，减去1..i-1里面选n次，这样剩下的就是至少选一次i片花瓣的次数了，

易知最后最有活力的花有i个花瓣的概率 P(i) = i ^ n - (i - 1) ^ n。那么有：

ans = 1 / (n ^ m) * \sum_{i = 1}^{m} (i ^ n - (i - 1) ^ n) * i

可以推出：

ans = m - \sum_{i = 0}^{m - 1} (i / m) ^ n

###Python 2.7 Code

#input
m, n = raw_input().split()
m = int(m)
n = int(n)

# ans = 1 / (n ^ m) * sigma(i = 1 ~ m) { [i ^ n - (i - 1) ^ n] * i }
# ==> n ** m * ans = m ** (n + 1) - sigma(i = 1 ~ m) { (i - 1) ^ n }
# ==> ans = m - sigma(i = 1 ~ m) { [(i - 1) / m] ^ n }
ans = m * 1.0

for i in range(0, m) :
ans -= (i * 1. / m) ** n

print "%.4f" % ans

不得不说Python确实很直观

等比数列求和，如果要计算最大活力值为\(i\)的概率，首项为\(\dfrac{m-i+1}{m}\),公比为\(\dfrac{i-1}{m}\),项数为\(n\),然后减去以前所有数的和。

Pascal Code

var
n,m:longint;
i:longint;
ans,sum,q,f:real;
a:array[1..100001] of real;
begin
readln(m,n);
sum:=0;
for i:=m downto 1 do
begin
q:=(i-1)/m;
f:=(m-i+1)/m;
if i=1 then a[i]:=f
else a[i]:=f*(1-exp(n*ln(q)))/(1-q);
a[i]:=a[i]-sum;
ans:=ans+a[i]*i;
sum:=sum+a[i];
end;
writeln(ans:0:4);
end.

###Code
#include<cstdio>
#include<cmath>
int main()
{
int m,n;
scanf("%d%d",&m,&n);
double ans=m;
for(int i=1;i<=m-1;i++)
ans-=pow((i+0.0)/m,n);
printf("%.4f",ans);
return 0;
}

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

const int N=100001;

int n,m;

double res,t[N];

double mi(double i,int k)

{

if (!k) return 1;

double ans=mi(i,k>>1);

return ans*ans*(k&1?i:1);

}

int main(void)

{

freopen("test.in","r",stdin);

scanf("%d%d",&m,&n);

for (int i=1;i<=m;i++) t[i]=mi((double)i/m,n);

for (int i=m;i;i--) res+=(double)i*(t[i]-t[i-1]);

printf("%0.4lf\n",res);

return 0;

}
http://shadowchaser.lofter.com/post/1d04e306_5df51b3

这个问题朴素地计算就行了. 选n次之后得到花瓣最多的花有k片花瓣的概率是(k^n-(k-1)^n)/m^n, 因为总共有m^n中选法, 而需要最多只有k片花瓣, 所以每次都得在1~k之内选, 选法有k^n种, 但是必须至少有一次选中了k片花瓣的花, 也就是不能每次都选中k-1以下的, 即减去(k-1)^n. 得出每个概率之后求期望就容易了, 最终得到m-((1/m)^n+(2/m)^n+...+((m-1)/m)^n). 用double计算不知道精度有没有问题...

数论+快速幂？

1234