BZOJ2720 列隊春遊 [期望][數學]

2720: [Violet 5]列隊春遊

Time Limit: 5 Sec   Memory Limit: 128 MB

Submit: 215   Solved: 152

[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

#include<bits/stdc++.h>
int i,n,s,x,c[]; 
double ans;
int main(){  
    scanf("%d",&n);   
    for(i=;i<=n;i++)scanf("%d",&x),c[x]++;n++;  
    for(i=;i<=;i++)  
        if(c[i])ans+=*c[i]*n/(n-s),s+=c[i];  
    printf("%.2lf\n",ans);
}
           

考慮對i有貢獻的j，

j< i則共有s個，

j>=i則共有n-s+1個，j必須在i中

則共有\( (n-s)! \)種排列，剩餘s-1個\( P^{s-1}_n \)種排列。

=>\( \frac {C*S*(n-s)!P^{s-1}_n }{n!} \) = \( \frac{C*S(n-s)!n! }{n!(n-s+1)!} \)

=>\( \frac{C*S}{n*S+1} \)

加上自己的貢獻：

\( \frac{C*S}{n*s+1}+\)=\( \frac{C*S}{n*s+1} + \frac{C*(n*s+1)}{n*s+1} \)

=>\( \frac{C*(n+1)}{n-s+1} \)