首页 > 代码库 > Codeforces Round #259(div2)C(数学期望)

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

2024-07-17 23:52:34   211人阅读

数学题。

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

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

这里的技巧在于：由于n<=105,   kn显然会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 intdouble m,n,ans=0;int main(){    //freopen("in3.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%lf%lf",&m,&n);    for(int i=1;i<=m;i++)    {        ans+=i*(pow(i/m,n)-pow((i-1)/m,n));    }    printf("%.12f\n",ans);    //fclose(stdin);    //fclose(stdout);    return 0;}

 


联系
我们