记忆化搜索+概率DP
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int c[],n,ff;
double dp[];
double solve(int f)
{
if(dp[f]>) return dp[f];
dp[f]=;
for(int i=;i<n;i++){
if(f>c[i]){
double t=(sqrt(5.0)+1.0)/*c[i]*c[i];
int p=(int)t;
dp[f]+=1.0*p/n;
}
else{
dp[f]+=(+solve(f+c[i]))/n;
}
}
return dp[f];
}
int main(){
while(scanf("%d%d",&n,&ff)!=EOF){
for(int i=;i<n;i++) cin>>c[i];
memset(dp,,sizeof(dp));
printf("%.3lf\n",solve(ff));
} return ;
}
