← 返回题目列表

Codeforces · 717/D

D. Dexterina 的实验室

中文机器翻译题面 查看原题

Dexterina 和 Womandark 自从认识以来一直是死对头。由于她们都是超级聪明的少女,她们一直试图以和平非暴力的方式解决争端。天知道他们给了彼此多少种不同的挑战,他们的分数是相等的,他们都拼命地想在各种斗智斗勇中击败对方。这一次,Dexterina 向 Womandark 发起了一场 Nim 游戏的挑战。

Nim 是一款两人游戏,玩家轮流从不同的堆中移除对象。每回合,玩家必须至少移除一个物体,并且可以从单个堆中移除任意数量的物体。无法完成回合的玩家就输了。根据他们的协议,堆的大小是从范围 [0, x] 中随机选择的。每堆的大小都是独立于游戏开始前已知的相同概率分布而得出的。

Womandark 正在想出一个全新的邪恶想法来阻止 Dexterina 的计划,所以她没有太多空闲时间。然而,她向你提供了一些让你看起来漂亮的秘诀,以换取帮助她在尼姆获胜。您的任务是告诉她,根据上述规则,第一个玩的玩家获胜的概率是多少。

输入

输入的第一行包含两个整数 n (1 ≤ n ≤ 109) 和 x (1 ≤ x ≤ 100) - 分别是堆的数量和堆中对象的最大数量。第二行包含 x + 1 个实数,每个实数最多保留 6 位小数:P(0)、P(1)、...、P(X)。这里,P(i) 是游戏开始时堆中正好有 i 个对象的概率。保证所有 P(i) 之和等于 1。

输出

输出一个实数,即第一个玩家获胜的概率。如果答案与正确答案相差最多 10 - 6 个,则判定为正确。

示例

输入 #1

2 2
0.500000 0.250000 0.250000

输出 #1

0.62500000