对 于 每 个 X i ， 第 k 名 贡 献 了 X i 。 我 们 设 第 l 位 到 第 r 位 的 水 平 都 是 X i ， 那 么 X i 被 选 中 的 概 率 为 p 2 , < X i 的 概 率 为 p 1 , > X i 的 概 率 为 p 3 。 这 种 情 况 的 概 率 为 p 1 l − 1 ∗ p 3 n − r ∗ p 2 r − l + 1 ∗ n ! / ( l − 1 ) ! / ( n − r ) ! / ( r − l + 1 ) ! 。 对于每个Xi，第k名贡献了X_i。 我们设第l位到第r位的水平都是X_i，那么Xi被选中的概率为p_2, <X_i的概率为p_1, >Xi的概率为p_3。 这种情况的概率为p_1^{l-1} * p3^{n-r} * p2^{r-l+1} *n!/(l-1)!/(n-r)!/(r-l+1)!。 对于每个Xi，第k名贡献了Xi。我们设第l位到第r位的水平都是Xi，那么Xi被选中的概率为p2,<Xi的概率为p1,>Xi的概率为p3。这种情况的概率为p1l−1∗p3n−r∗p2r−l+1∗n!/(l−1)!/(n−r)!/(r−l+1)!。 我们把这个概率加到l到r位就可以了。 直接算可能会爆double，需要用long double或者求对数。pow特别慢直接用会超时 一开始我就写了个十分暴力，还挂了
#include<iostream> #include<iomanip> using namespace std; const int maxn=2011; const int maxm=2011; long double pow(long double v,int k) { long double ret=1.0,t=v; while(k) { if(k&1) ret*=t; t*=t; k>>=1; } return ret; } long double fabs(long double a) { return (a<0.0L)?(-a):a; } int N, M; long double Pow[maxm]; long double Q[maxm],X[maxm],SumQ[maxn]; long double C[maxn][maxn]; long double Val[maxn][maxm],Temp; int main(){ cin>>N>>M; for(int i=0;i<=N;++i) { C[i][0]=1.0L; C[i][i]=1.0L; for(int j=1;j<i;++j) { C[i][j]=C[i-1][j]+C[i-1][j-1]; } } for(int i=1;i<=M;++i) cin>>Q[i]>>X[i]; SumQ[0]=0.0L; for(int i=1;i<=M;++i) SumQ[i]=SumQ[i-1]+Q[i]; for(int i=1;i<=M;++i) { Q[i]/=SumQ[M]; SumQ[i]/=SumQ[M]; } for(int p=0;p<M;++p) for(int i=0;i<N;++i) Val[i+1][p+1]=C[N][i]*pow(SumQ[p], i)*pow(SumQ[M]-SumQ[p], N-i); for(int p=1;p<=M;++p) for(int i=2;i<=N;++i) Val[i][p]+=Val[i-1][p]; for(int i=1;i<=N;++i) for(int p=1;p<M;++p) Val[i][p]-=Val[i][p+1]; long double Ans=0.0L; for(int i=1;i<=N;++i) { Temp=0.0L; for(int p=1;p<=M;++p) { Temp+=Val[i][p]; if(Temp>=0.5L) { Temp=X[p]; break; } } for(int p=1;p<=M;++p) { Ans+=fabs((long double)(X[p])-Temp)*Val[i][p]; } } cout<<fixed<<setprecision(9)<<Ans<<endl; return 0; }来源：zr
