CF453A Little Pony and Expected Maximum 数学题
这个题比较水。连我都能做出来
这个题我们直接考虑最大值为 \(k\) 时的概率是多少。
我们设 \(p_k\) 为最大值为 \(k\) 时的概率。令 \(f_k\) 表示 \(m\) 到 \(k\) 的所有值一个也没有出现的概率。
如果最大值为 \(k\) ,那么说明比 \(k\) 大的数一个也没有出现,而 \(k\) 至少出现一次。
也就是说,\(f_{k+1}\) 这个概率里包含两个部分,其中一个部分是 \(f_k\) ,也就是 \(k\) 没有出现,另一个部分是 \(k\) 至少出现一次。也就是说 \(f_{k+1}-f_{k}\) 就是 \(k\) 为最大值的概率。
我们用快速幂一算就可以。
代码:
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 100010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int m,n;
dd p[N],ans;
inline dd ksm(dd a,int b){
dd res=1.0;
while(b){
if(b&1) res*=a;
a=a*a;
b>>=1;
}
return res;
}
int main(){
read(m);read(n);
p[m+1]=1;
for(int i=m;i>=1;i--){
p[i]=ksm((dd)(i-1)/(dd)m,n);
ans+=(p[i+1]-p[i])*i;
}
printf("%lf\n",ans);
return 0;
}