第一种解法是$O(n^3*p)$的：
f[i][j][k]表示前i个人进j个人长度为k有几种方案（排列固定为123..n时）。
$f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-a[i]]$
最外层枚举t表示被卡的那个人。i=t时不加上f[i-1][j-1][k-a[i]]。
$ans={{(\sum f[n][j][k]*j*j!*(n-1-j)!)+(\sum f[n][n][k]*n)}}/(n!)$。
可以看看这篇题解
#include<cstdio> #include<cstring> #define N 55 int n,p,a[N]; double f[N][N][N],ans,c[N]= {1}; int main(){ scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d",&a[i]); c[i]=c[i-1]*i; } scanf("%d",&p); for(int t=0; t<=n; t++){ memset(f,0,sizeof f); f[0][0][0]=1; for(int i=1; i<=n; i++) for(int j=0; j<=i; j++) for(int k=0; k<=p; k++){ f[i][j][k]=f[i-1][j][k]; if(j>=1&&t!=i&&k>=a[i])f[i][j][k]+=f[i-1][j-1][k-a[i]]; } for(int j=1; j<n; j++) for(int k=1; k<=p; k++)if(a[t]+k>p) ans+=c[j]*c[n-1-j]/c[n]*f[n][j][k]*j; for(int k=1; k<=p; k++)ans+=f[n][n][k]*n; } printf("%lf",ans); }
还可以更高效，$O(n^2*p)$
参考题解
f[i][j][k]表示前i个人至少进j个人这j个人的长度和为k有几种方案（排列为123..n时）。
那么$ans=(\sum f[n][j][k]*j!*(n-j)!/(n!)$。
我原来不太理解为什么至少j个人就是这么推，问了下队友，说是因为没有卡后面的，所以有可能可以进更多人。
其实第一种方法算的f也是至少j个人，然后在后面累加ans时再卡住第j+1个人。
并且可以用滚动数组优化为2维数组。
#include<cstdio> #define N 51 int n,a[N],p; double fac[N]= {1},f[N][N],tol,ans; int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",a+i); fac[i]=fac[i-1]*i; tol+=a[i]; } scanf("%d",&p); if(tol<=p) { printf("%d",n); return 0; } f[0][0]=1; for(int i=1; i<=n; i++) for(int j=n-1; j>=0; j--) for(int k=0; k+a[i]<=p; k++) f[j+1][k+a[i]]+=f[j][k]; for(int j=1; j<=n; j++) for(int k=0; k<=p; k++) ans+=f[j][k]*fac[j]*fac[n-j]; ans/=fac[n]; printf("%lf",ans); }