记录编号	373159	评测结果	AAAAAAAAA
题目名称	[SYZOI Round1]组合数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-02-20 10:45:25	内存使用	0.30 MiB

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
struct poly{
  int k;
  vector<LL> a;
  inline void setk(int nk){
    k = nk;
    a.resize(nk+1);
  }
  poly conv(poly &p){
    poly r;
    r.setk(k+p.k);
    fill(r.a.begin(), r.a.end(), 0);
    for(int i = 0; i <= k; i++)
      for(int j = 0; j <= p.k; j++)
        r.a[i+j] += a[i]*p.a[j];
    return r;
  }
};
int main(){
  freopen("conbination.in", "r", stdin);
  freopen("conbination.out", "w", stdout);
  poly r;
  r.setk(0);
  r.a[0] = 1; //r = 1;
  int n; 
  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    int x; 
    scanf("%d", &x);
    poly t; t.setk(x);
    t.a[0] = 1;
    t.a[x] = 1;
    r = r.conv(t);
  }
  LL L, R;
  LL tot = 0, in = 0;
  scanf("%lld %lld", &L, &R);
  for(int i = 0; i <= r.k; i++){
    if(i >= L && i <= R)in += r.a[i];
    tot += r.a[i];
  }
  printf("%.4lf\n", 1.0*in/tot);
  return 0;
}