#abc126c. [abc126_c]Dice and Coin

[abc126_c]Dice and Coin

Snuke 有一个 nn 面的色子,投掷这个色子的时候会以相等的概率得到一个在 11nn 之间的整数。他还有一个硬币,投掷时正面朝上和反面朝上的概率相等。

现在他要用色子和硬币玩一个游戏:

  • 扔色子,将得到的整数作为初始分数。

  • 只要这个分数在 11k1k-1 之间(包含 11k1k-1),就扔硬币。当正面朝上时,将这一分数翻倍;否则,将分数归零。

  • 分数归零或大于等于 kk 时,游戏结束。若分数大于等于 kk,Snuke 获胜,否则 Snuke 失败。

给出 nnkk,你需要求出 Snuke 获胜的概率。