P12796 [NERC 2022] Game of Questions

Genie 正在参加一个智力游戏。游戏包含 $n$ 个问题，有 $m$ 名从 $1$ 到 $m$ 编号的参赛者。Genie 是 $1$ 号参赛者。 对于每个问题 $i$ 和参赛者 $j$，已知该参赛者是否会正确回答该问题。 游戏的目标是成为坚持到最后的参赛者之一。 游戏按如下方式进行。首先，所有 $n$ 个问题会被随机均匀打乱（所有 $n!$ 种排列都是等可能的）。然后，问题会一个接一个地被提出。每位参赛者都会回答问题。如果所有仍在游戏中的参赛者都回答正确，或都回答错误，则什么也不会发生。否则，回答错误的参赛者将输掉并离开游戏。 在所有 $n$ 个问题都被问完后，所有仍在游戏中的参赛者都被宣布为获胜者。 Genie 赢得游戏的概率是多少？

第一行包含两个整数 $n$ 和 $m$——问题的数量和参赛者的数量 ($1 \le n \le 2 \cdot 10^5$; $2 \le m \le 17$)。 接下来的 $n$ 行中的第 $i$ 行包含 $m$ 个字符 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, m}$。如果参赛者 $j$ 正确回答了问题 $i$，则字符 $s_{i, j}$ 为 $\tt{1}$，否则为 $\tt{0}$。

输出 Genie 赢得游戏的概率。如果你的答案的绝对或相对误差不超过 $10^{-9}$，则该答案将被认为是正确的。

在第一个样例中，只有一个问题，Genie 会正确回答，因此赢得比赛（与参赛者 $2$ 和 $4$ 一起）。 在第二个样例中，一名参赛者将在第一个被问到的问题后离开，另一名参赛者将在第二个被问到的问题后离开。每位参赛者获胜的概率为 $\frac{1}{3}$。 翻译由 gemini2.5pro 完成