Игра вопросов
Игра вопросов
Джинн принимает участие в интеллектуальной игре. Игра состоит из n вопросов, и в ней участвует m участников, пронумерованных от 1 до m. Джинн - участник под номером 1.
Для каждого вопроса i и участника j известно, ответит ли участник на вопрос правильно или нет.
Цель игры - остаться последним участником, оставшимся в игре.
Игра проводится следующим образом. Во-первых, все n вопросов равномерно перемешиваются случайным образом (все перестановки n! равновероятны). Затем вопросы задаются один за другим. Каждый участник отвечает на вопрос. Если все участники еще в игре отвечают на вопрос правильно или если все они отвечают на вопрос неправильно, ничего не происходит. В противном случае те участники, которые ответят на вопрос неправильно, проигрывают и выбывают из игры.
После того, как будут заданы все n вопросов, все участники, оставшиеся в игре, объявляются победителями.
Какова вероятность того, что Джинн выиграет игру?
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 2 * 105
, 2 ≤ m ≤ 17) - количество вопросов и количество участников.
i-я из следующих n строк содержит m символов si,1
, si,2
, ..., si,m
. Символ si,j
равен 1, если участник j правильно ответил на вопрос i, или 0 иначе.
Выходные данные
Выведите вероятность того, что Джинн выиграет игру. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10-9
.
Пояснение
В первом примере есть один вопрос, и Джин ответит на него правильно, тем самым выиграв игру (вместе с участниками 2 и 4).
Во втором примере один участник уйдет после первого заданного вопроса, а другой участник уйдет после второго заданного вопроса. Каждый участник выиграет с вероятностью 1 / 3.
1 5 11010
1.0000000000000000
3 3 011 101 110
0.3333333333333333
6 4 1011 0110 1111 0110 0000 1101
0.1666666666666667