算出来每个数被计算答案的期望次数就可以
考虑这个次数，我们可以把一次合并反过来看，变成把一个数+1然后再复制一个
记f[i][j]为一共n个数时第j个数的期望次数，就可以得到期望的递推公式，最后拿f[N]乘一乘就行了
要注意每一位的期望次数是不一样的..不存在什么中间的次数一样之类的...
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define lowb(x) ((x)&(-(x))) 4 #define REP(i,n0,n) for(i=n0;i<=n;i++) 5 #define PER(i,n0,n) for(i=n;i>=n0;i--) 6 #define MAX(a,b) ((a>b)?a:b) 7 #define MIN(a,b) ((a<b)?a:b) 8 #define CLR(a,x) memset(a,x,sizeof(a)) 9 #define rei register int 10 using namespace std; 11 typedef long long ll; 12 const int maxn=5050; 13 14 inline ll rd(){ 15 ll x=0;char c=getchar();int neg=1; 16 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 17 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 18 return x*neg; 19 } 20 21 int N,a[maxn]; 22 double f[2][maxn]; 23 24 int main(){ 25 //freopen(".in","r",stdin); 26 rei i,j,k; 27 N=rd(); 28 for(i=1;i<=N;i++) a[i]=rd(); 29 30 if(N<=2){ 31 printf("%.5lf",1.0*(a[1]+a[2])); 32 return 0; 33 } 34 f[1][1]=f[1][2]=1; 35 bool b=0; 36 for(i=3;i<=N;i++){ 37 f[b][1]=((f[b^1][1]+1)+f[b^1][1]*(i-2))/(i-1); 38 for(j=2;j<i;j++){ 39 f[b][j]=((f[b^1][j-1]+1)+(f[b^1][j]+1)+(f[b^1][j-1])*(j-2)+(f[b^1][j])*(i-j-1))/(i-1); 40 // printf("%d %d %lf ",i,j,f[b][j]); 41 } 42 f[b][i]=(f[b^1][i-1]*(i-2)+f[b^1][i-1]+1)/(i-1); 43 // for(j=1;j<=i;j++) printf("%d %d %lf ",i,j,f[b][j]); 44 // f[b][i]=((f[b^1][i])*(N-2))/(N-1); 45 b^=1; 46 }double ans=0; 47 for(i=1;i<=N;i++){ 48 ans+=f[b^1][i]*a[i]; 49 } 50 printf("%.5lf ",ans); 51 return 0; 52 }