В этой теме описано, как пройтись по всем подмаскам данной маски без дополнительных памяти и времени. Мне стало нужно сделать то же самое для надмасок, но я не нашёл ничего подобного. Исходя из формулы mask ^ (~mask) = -1, мой брат сгенерировал следующий код:
for (int over = (1 << n) - 1; over > 0; over = ((over - mask - 1) & ~mask) + mask) {
cout << over << " ";
}
Это и правда работает. Но нельзя ли это как-то упростить, чтобы было легче вспомнить это на контесте?
Автокомментарий: текст был обновлен пользователем rembocoder (предыдущая версия, новая версия, сравнить).
Пройдитесь по всем подмаскам инверсии данной, а в ответ выводите ксор текущей и данной.
Да, это более простая версия для запоминания той же идеи)
.
There is an easier code ==>
for(int over = mask;over > 0;over = (over -1) & mask) cout << over << " ";
Also, you can prove it by induction.
Genial, thank you.
you want the overmasks of $$$S$$$ (i.e.: the masks of which $$$S$$$ is submask). I think it's the same as the NOT ($$$\text{~}$$$) of submasks of $$$\text{~} S$$$. Correct me if I'm wrong.
This post has no comment newer than 8 months ago. How did it appear under "Recent actions"?
Probably someone posted a comment and deleted it.
Or OP made an edit.