Постановка задачи

Пусть задан неориентированный граф на $$$n$$$ вершинах с помощью матрицы смежности. Необходимо найти количество клик в нём (включая пустое множество).

Общая идея

Воспользуемся методом MITM, как описано здесь. Таким образом, можно получить асимптотику $$$O(2^{\frac n2}n)$$$.

Улучшим подсчет массива $$$dp\text{_}sum[mask]$$$ — количество клик в подграфе, заданном маской, до асимптотики $$$O(2^{\frac n2}) \,$$$ вместо подсчета за $$$O(2^{\frac n2} n$$$) таким способом. Так, общее время решения сократится до $$$O(2^{\frac n2})$$$.

Алгоритм подсчета:

1. $$$dp\text{_}sum[0] = 1$$$
2. Пусть вершины, заданные маской, образуют клику. Тогда $$$dp\text{_}sum[mask] = dp\text{_}sum[mask \oplus last\text{_}bit] * 2$$$, где $$$last\text{_}bit$$$ — последний ненулевой бит
3. Пусть вершины, заданные маской, не образуют клику. Тогда найдутся две вершины $$$u$$$ и $$$v$$$, между которыми нет ребра. Обозначим за $$$bit_u, bit_v$$$ маски, отвечающие за набор из вершин $$$u$$$ и $$$v$$$ соответственно. В таком случае, $$$dp\text{_}sum[mask] = dp\text{_}sum[mask \oplus bit_u] + dp\text{_}sum[mask \oplus bit_v] - dp\text{_}sum[mask \oplus bit_u \oplus bit_v]$$$

Очевидно, что если научиться находить по маске две вершины, между которыми нет ребра, то время подсчета $$$dp\text{_}sum$$$ будет $$$O(2^{\frac n2})$$$, что и требовалось.

Решение

Будем поддерживать массив $$$intersection[mask]$$$ — маска, задающая множество вершин, соединенных с каждой вершиной из $$$mask$$$.
Тогда подграф, заданный маской, не является кликой $$$\iff$$$ $$$mask \not \subset intersection[mask]$$$ $$$\iff$$$ $$$mask \cap (mask \oplus intersection[mask]) = diff\text{_}mask \not = 0$$$

Заметим, что единичные биты в $$$diff\text{_}mask$$$ задают вершины из mask, которые не соединены со всеми остальными. Возьмем одну из них (например, последний ненулевой бит $$$diff\text{_}mask$$$) и обозначим ее за $$$u$$$.
Чтобы найти вторую вершину, достаточно рассмотреть такое выражение: $$$mask \text{&} (graph\text{_}u \oplus mask)$$$, где $$$graph\text{_}u$$$ — "маска смежности" вершины $$$u$$$ (i-ый бит ненулевой $$$\iff$$$ вершины $$$u$$$ и $$$i$$$ соединены).
Тогда единичные биты в получившемся выражении соответствуют вершинам в нашем наборе, которые не соединены с вершиной $$$u$$$ — можно взять последний

Honourable mentions

1. Последний бит $$$mask$$$ можно получить так: $$$mask \, \text{&} \, (-mask)$$$
2. $$$\oplus$$$ — операция xor, & — операция "логического и"