http://mirror.codeforces.com/contest/844/problem/B Не смог ее решить контесте, правильно. Но и не понимаю, как это сделать. Возможно я не прав, в том смысле, что не понимаю зачем нужен блог, прошу не гневаться если это так и сюда нельзя задавать такие вопросы. Так же прошу не приводить полное решение, а лишь навести на мысль, ссылку на мат тему, или просто ее название.
Заранее спасибо ))
Для каждой строки и для каждого столбца посчитаем количество единиц и нулей в них.
Сколькими способами можно выбрать непустое подмножество из K элементов?
2^k — 1
Каждый элемент матрицы будет подсчитан дважды, поэтому вычтем m*n.
То есть циклы для 0 и 1, в каждом из которых от 1 до k, где k счетчик в циклах для 0, 1? Тогда O(n)=V^3, где V=m*n, я правильно понял?
Нет. Пусть в множестве есть K элементов. Выбрать непустое подмножество можно 2^K — 1 способами.
Посчитать количество единиц и нулей в каждой строке и в каждом столбце можно за О(n*m)
row[i][0] += (a[i][j] == 0); row[i][1] += (a[i][j] == 1); col[j][0] += (a[i][j] == 0); col[j][1] += (a[i][j] == 1);
ответом будет являться сумма 2^row[i][0] — 1 + 2^row[i][0] — 1 по всем i + сумма 2^col[j][0] — 1 + 2^col[j][1] — 1 по всем j
Ну и вычесть n*m.