Программа Php для подсчета наборов 1 и 0 в двоичной матрице

Опубликовано: 20 Сентября, 2022

Учитывая двоичную матрицу × m, подсчитайте количество наборов, в которых набор может быть сформирован из одного или нескольких одинаковых значений в строке или столбце.
Примеры:

Input: 1 0 1
       0 1 0 
Output: 8 
Explanation: There are six one-element sets
(three 1s and three 0s). There are two two-
element sets, the first one consists of the
first and the third cells of the first row.
The second one consists of the first and the 
third cells of the second row. 

Input: 1 0
       1 1 
Output: 6

 

Количество непустых подмножеств x элементов равно 2 x – 1. Мы обходим каждую строку и вычисляем количество ячеек с единицами и нулями. Для каждых u нулей и v единиц общее количество наборов равно 2 u – 1 + 2 v – 1. Затем мы проходим по всем столбцам, вычисляем одинаковые значения и вычисляем общую сумму. Наконец, мы вычитаем mxn из общей суммы, так как отдельные элементы учитываются дважды.

Выход:

8

Временная сложность: O(n * m)
Пожалуйста, обратитесь к полной статье о подсчете наборов 1 и 0 в двоичной матрице для получения более подробной информации!

PHP