P15878 [ICPC 2026 NAC] Draw Your Deck

你正在玩一个单人纸牌游戏。牌堆中有 $N$ 张牌，每张牌上写有一个 $0$ 到 $K$ 之间的整数。你洗牌后抽一张牌，这张牌构成你的起始手牌。然后你通过反复选择并弃置手牌中的一张牌来进行游戏。每次弃牌时，你从牌堆顶摸取与弃牌上所写数字相同数量的牌放入手牌（如果牌堆剩余牌数不足，则全部摸完）。如果你摸空了牌堆，你就获胜；如果牌堆中还有牌但你的手牌已空，你就失败。给定牌堆的内容，假设所有可能的洗牌方式等概率出现，并且你采取最优策略，请问你获胜的概率是多少？

第一行包含两个空格分隔的整数 $N$ 和 $K$，其中 $N$ $(1 \leq N \leq 1500)$ 是牌堆中的牌数，$K$ $(0 \leq K \leq 3)$ 是牌面上出现的最大整数。 第二行包含 $K+1$ 个空格分隔的整数 $a_i$ $(0 \leq a_i \leq N)$，从 $i=0$ 开始依次给出：牌堆中写有数字 $i$ 的牌的数量。保证 $a_K > 0$，且所有 $a_i$ 之和为 $N$。

输出一个实数：在你采取最优策略时获胜的概率。如果你的答案与标准答案的绝对误差不超过 $10^{-6}$，则视为正确。

翻译由 DeepSeek V3.2 完成