Codeforces Round #259(div2)C(数学期望)

数学题。

关键是求最大值为k时有多少种情况，结果是kⁿ-(k-1)^n-1。可以这么想：每一次都从1至k里选，共kⁿ种，这里需要再减去每一次都从1至k-1里面选的情况。当然也可以分类计数法：按出现几次k来分类，然后逆着用一下二项式定理得出结论。

整个的期望是Σk(kⁿ-(k-1)^n-1)/mⁿ,其中k=1......n。

这里的技巧在于：由于n<=10⁵, kⁿ显然会RE，那么就先把分母除上，每次算一个小于1的浮点数的n次方，肯定不会RE。C++中乘方用pow函数算是很快的。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

using namespace std;

#define INF 1000000000

#define eps 1e-8

#define pii pair<int,int>

#define LL long long int

double m,n,ans=;

int main()

{

    //freopen("in3.txt","r",stdin);

    //freopen("out.txt","w",stdout);

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

    for(int i=;i<=m;i++)

    {

        ans+=i*(pow(i/m,n)-pow((i-)/m,n));

    }

    printf("%.12f\n",ans);

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

巴特西

Codeforces Round #259(div2)C(数学期望)

最新文章

热门文章