← 返回题目列表

Codeforces · 1773/G

G. 问题游戏

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

精灵正在参加智力游戏。游戏由$$$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}$$$。字符 $$$s_{i, j}$$$ 是 '1' 如果参与者 $$$j$$$ 正确回答问题 $$$i$$$ 或 '0'否则。

输出

打印 Genie 赢得比赛的概率。如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。

示例

输入
复制

1 5
11010

输出
复制

1.0000000000000000

输入
复制

3 3
011
101
110

输出
复制

0.3333333333333333

输入
复制

6 4
1011
0110
1111
0110
0000
1101

输出
复制

0.1666666666666667

注意

在第一个示例中,有一个问题,Genie 将正确回答它,从而赢得游戏(以及参与者 $$$2$$$ 和 $$$4$$$)。

在第二个示例中,一名参与者将在提出第一个问题后离开,另一名参与者将在提出第二个问题后离开。每个参与者获胜的概率为 $$$\frac{1}{3}$$$。