[THUPC 2023 初赛] 公平合作

在大地的尽头，一座灰白的灯塔矗立在漫长的海岸线上。这一片海域海流复杂、礁石嶙峋，却又是不少航线的必经之路。若没有如此高耸而明亮的灯塔为过路的船只照亮航路，或许会有更多不幸的生命葬身海底。为了看管好这一座海上明灯，一批训练有素的守望人轮流值守于此。日复一日的工作枯燥乏味却又不能有丝毫闪失，紧绷的神经直到下一班守望人到来才得以放松。 在电力普及之前，灯塔通常使用煤油灯为过往的水手指引前行的方向。每次为这座灯塔添加燃油时，需要两位守望人各自搬运一个容积为 $L$ 的油桶；而每次轮到 Y 和 S 所在的班组照料这座灯塔时，总是由 Y 和 S 负责为灯塔加油。将煤油搬运至灯室时，如果不装满油桶，对灯塔的正常运转也没有太大影响，无非是需要多来回搬运几趟。但是，如果两位守望人都想着偷懒，问题恐怕就不只是多几趟那么简单。Y 和 S 想到了一个好办法：互相为对方的油桶装油。 灯塔里有 $N$ 个用于将储存的煤油转移到油桶中的容器，其中第 $i$ 个容器的容积为 $a_i$。Y 和 S 先想办法决定由谁先装油。两人先后装油；轮到其中一位守望人装油时，这位守望人每次从所有容器中等概率地随机选出一个容器，将其装满油，并全部倒入对方的油桶中。两位守望人都可以在操作任意多次（可以是 0 次）后结束装油，但后手必须等先手结束后才能开始装油。Y 和 S 先后装完煤油后，两人会比一下谁把对方的油桶装得更满，再各自把自己的油桶搬运到灯室。但是，如果有谁某次选出一个容器后，把对方的油桶装满了，但容器里还有没倒出的煤油，那么这位倒霉的守望人就必须把两个油桶都独自搬到灯室——这也算是为单调的生活平添了几分乐趣。显然，如果先手某次随机选中的容器会使得油桶溢出，那么后手可以往先手的油桶里面装任意量的煤油，然后幸灾乐祸；因此我们约定：当先手溢出时，必定由先手搬两个油桶。 现在只剩下了一个问题：当 Y 和 S 都采取最优策略，使得对方搬的煤油尽可能地比自己多的时候，先手搬的煤油不多于后手的概率是多大？ ## Input 输入的第一行包括两个正整数 $N$ 和 $L$，分别表示转移用的容器数量和油桶的容积。 输入的第二行包括 $N$ 个正整数 $a_1, \cdots, a_N$，分别表示每个转移用的容器的容积。 ## Output 输出一个实数，表示先手搬的煤油不多于后手的概率。当你的输出与标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。 [samples] ## Note #### 样例解释 1 可以证明，此时先手的策略一定是装满对方的油桶，且装满时必胜。经过若干次随机抽取后，能恰好将对方的油桶装满的概率为： $$ \left(\frac{1}{2}\right)^2 + \binom{3}{1}\left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 = \frac{11}{16}=0.6875 $$ #### 数据范围 对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^3$，$1\le L\le 10^9$，$1\le a_i\le 2\times 10^3$。 #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。