daily 1

CF 261B

$dp[i][j][k]$表示处理了前i个数，当前选择了前j个数，剩余的大小为k的方案数，那么我们的答案就是把所有的$dp[i][j][k]$加起来除以$n!$即可

void solve(){
  ll n,p;
  cin>>n;
  vector<int>a(n+1);
  vector<double>fac(n+1);
  fac[0]=fac[1]=1;
  ll sum=0;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    fac[i]=fac[i-1]*i;
    sum+=a[i];
  }
  cin>>p;
  if(sum<=p){
    cout<<n<<'\n';
    return;
  }
  vector dp(n+1,vector<ll>(p+1,0));
  dp[0][0]=1;
  for(int i=1;i<=n;++i){
    for(int j=i;j>=1;--j){
        for(int v=p;v>=a[i];--v){
            dp[j][v]+=dp[j-1][v-a[i]];
        }
    }
  }
  double ans=0;
  for(int i=1;i<=n;++i){
    for(int j=0;j<=p;++j){
        ans+=(double)dp[i][j]*fac[i]*fac[n-i];
    }
  }
  cout<<ans/fac[n]<<'\n';
  return;
}