CF2115C Gellyfish and Eternal Violet

在 Gellyfish 面前有 $n$ 只怪物，编号从 $1$ 到 $n$，第 $i$ 只怪物的生命值为 $h_i$。 Gellyfish 并不想杀死它们，但她想让这些怪物对自己不再构成威胁。因此，她希望把所有怪物的生命值都恰好降到 $1$。 现在，Gellyfish 拿着“泪水磨砺之剑”，准备攻击怪物 $m$ 回合。每一回合： 1. “泪水磨砺之剑”有概率 $p$ 闪耀。 2. Gellyfish 可以选择是否攻击： - 如果 Gellyfish 不攻击，则什么都不会发生。 - 如果 Gellyfish 选择攻击且“泪水磨砺之剑”闪耀，则所有怪物的生命值都会减少 $1$。 - 如果 Gellyfish 选择攻击且“泪水磨砺之剑”没有闪耀，则 Gellyfish 可以选择其中一只怪物，使其生命值减少 $1$。 请注意，在 Gellyfish 决定是否攻击之前，她会知道剑是否闪耀。此外，当剑闪耀时，Gellyfish 只能对所有怪物进行攻击，不能只攻击其中一只怪物。 现在，Gellyfish 想知道，如果她在战斗中每一步都做出最优选择，最终达成目标的概率是多少。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $p'$（$1 \leq n \leq 20$，$1 \leq m \leq 4000$，$0 \leq p' \leq 100$），分别表示怪物的数量、攻击的回合数，以及“泪水磨砺之剑”闪耀的概率 $p = \frac{p'}{100}$。 每个测试用例的第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$1 \leq h_i \leq 400$），表示每只怪物的生命值。 保证所有测试用例中 $n$ 的总和不超过 $100$。

对于每个测试用例，输出一个实数，表示 Gellyfish 达成目标的概率。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 形式化地说，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，判为正确。

在第一个测试用例中，Gellyfish 在第一回合无论剑是否闪耀都会选择攻击。 如果第一回合剑闪耀，则 Gellyfish 在第一回合攻击后就能达成目标。 否则，如果第一回合剑没有闪耀，她会在第一回合攻击第 $1$ 只怪物。对于第二回合： - 如果剑闪耀，由于第 $1$ 只怪物在第一回合被攻击过，Gellyfish 无法达成目标。 - 否则，她可以攻击第 $2$ 只怪物，从而达成目标。 因此，Gellyfish 达成目标的概率为 $10\% + (90\% \cdot 90\%) = 91\%$。 在第二个测试用例中，Gellyfish 只会在第一次剑闪耀时选择攻击。可以发现，唯一无法达成目标的情况是 $5$ 回合中剑从未闪耀。Gellyfish 达成目标的概率为 $100\% - (80\%)^5 = 67.232\%$。 由 ChatGPT 4.1 翻译