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