Game of Questions

题意翻译

### 题目描述 Genie 正在参加一个问答比赛。比赛共 $n$ 题，有 $m$ 个参赛者（Genie 为 $1$ 号参赛者）。 比赛的形式如下：先将 $n$ 道题随机排序（即每个排列出现的概率都是 $\dfrac{1}{n!}$），然后按排列的顺序会依次问出这 $n$ 个问题。问一个问题时，若所有人都会或所有人都不会则无事发生，否则不会的人会被淘汰。在 $n$ 个问题都被问完之后，未被淘汰的人就都赢得胜利。 现在给出每个人是否会每道题，请求出 Genie 获胜的概率。 ### 输入格式 第一行两个整数 $n,m$（$1\le n\le 2\cdot 10^5$；$2\le m\le 17$），表示参赛人数和题目数量。 接下来一个 $n\times m$ 的 01 矩阵，第 $i$ 行第 $j$ 个数 $s_{i,j}$ 表示第 $i$ 名选手会不会第 $j$ 题（$s_{i,j}=1$ 表示会，否则表示不会）。 ### 输出格式 输出 Genie 获胜的概率。答案是正确的当且仅当其与标准答案的差的绝对值在 $10^{-9}$ 以内。 ### 说明/提示 样例 $1$ 中，只有一个问题，故问题的顺序只有一种可能。问这个问题后第三、五名参赛者会被淘汰，Genie 和第二、四名选手一起获得胜利，故 Genie 获胜的概率为 $1$。 样例 $2$ 中，不管问题以哪种顺序问出，问的第一个问题会淘汰一个人，问的第二个问题又会淘汰一个人，剩下那个人获胜。则 Genie 获胜的概率等于第一个问题被第三个问出的概率，即 $\frac{1}{3}$。

题目描述

Genie is taking part in an intellectual game. The game consists of $ n $ questions, and there are $ m $ participants numbered from $ 1 $ to $ m $ . Genie is the participant number $ 1 $ . For each question $ i $ and participant $ j $ , it is known whether the participant will answer the question correctly or not. The goal of the game is to be the last participant staying in the game. The game is conducted as follows. First, all $ n $ questions get shuffled uniformly at random (all $ n! $ permutations are equally likely). Then, the questions are asked one by one. Each participant answers the question. If all participants still in the game answer the question correctly, or if all of them answer the question incorrectly, nothing happens. Otherwise, those participants who answer the question incorrectly lose and leave the game. After all $ n $ questions are asked, all participants who are still in the game are declared to be the winners. What is the probability that Genie will win the game?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ — the number of questions and the number of participants ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 2 \le m \le 17 $ ). The $ i $ -th of the next $ n $ lines contains $ m $ characters $ s_{i, 1}, s_{i, 2}, \ldots, s_{i, m} $ . Character $ s_{i, j} $ is '1' if participant $ j $ answers question $ i $ correctly or '0' otherwise.

输出格式

Print the probability that Genie will win the game. Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-9} $ .

输入输出样例

输入样例 #1

1 5
11010

输出样例 #1

1.0000000000000000

输入样例 #2

3 3
011
101
110

输出样例 #2

0.3333333333333333

输入样例 #3

6 4
1011
0110
1111
0110
0000
1101

输出样例 #3

0.1666666666666667

说明

In the first example, there is a single question and Genie will answer it correctly, thus winning the game (along with participants $ 2 $ and $ 4 $ ). In the second example, one participant will leave after the first asked question, and another participant will leave after the second asked question. Each participant will win with probability $ \frac{1}{3} $ .