F2. Мудрецы (усложненная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложненная версия задачи. Две версии отличаются ограничением на число мудрецов и ограничением по времени. Вы можете взламывать по этой задаче только если обе версии решены.

$$$n$$$ мудрецов живут в красивом городе. Некоторые из них знают друг друга.

Для всех возможных $$$n!$$$ перестановок $$$p_1, p_2, \ldots, p_n$$$ мудрецов, построим бинарную строку длины $$$n-1$$$: для всех $$$1 \leq i < n$$$ положим $$$s_i=1$$$ если мудрецы $$$p_i$$$ и $$$p_{i+1}$$$ знают друг друга, и $$$s_i=0$$$ иначе.

Для всех $$$2^{n-1}$$$ возможных бинарных строк, найдите число перестановок, при которых получается такая бинарная строка.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$2 \leq n \leq 18)$$$ — количество мудрецов в городе.

Следующие $$$n$$$ строк содержат бинарные строки, по $$$n$$$ символов в каждой, $$$j$$$-й символ в $$$i$$$-й строке равен «1» если мудрец $$$i$$$ знает мудреца $$$j$$$, и равен «0» иначе.

Гарантируется, что если $$$i$$$-й мудрец знает $$$j$$$-го мудреца, то $$$j$$$-й мудрец знает $$$i$$$-го мудреца, и никакой мудрец не знает сам себя.

Выходные данные

Выведите $$$2^{n-1}$$$ целых чисел, разделенных пробелами. Для каждого $$$0 \leq x < 2^{n-1}$$$:

  • Рассмотрим такую строку $$$s$$$ длины $$$n-1$$$, что $$$s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$$$ для $$$1 \leq i \leq n - 1$$$.
  • $$$(x+1)$$$-е число должно быть необходимому ответу для $$$s$$$.
Примеры
Входные данные
3
011
101
110
Выходные данные
0 0 0 6
Входные данные
4
0101
1000
0001
1010
Выходные данные
2 2 6 2 2 6 2 2
Примечание

В первом тесте все мудрецы знакомы, соответственно для всех перестановок получается строка $$$11$$$.

Во втором тесте

  • Если $$$p = \{1, 2, 3, 4\}$$$, строка будет равна $$$101$$$, потому что мудрецы $$$1$$$ и $$$2$$$ знакомы, $$$2$$$ и $$$3$$$ не знакомы, $$$3$$$ и $$$4$$$ знакомы;
  • Если $$$p = \{4, 1, 2, 3\}$$$, строка будет равна $$$110$$$, потому что мудрецы $$$1$$$ и $$$4$$$ не знакомы, $$$1$$$ и $$$2$$$ не знакомы, $$$2$$$ и $$$3$$$ не знакомы;
  • Если $$$p = \{1, 3, 2, 4\}$$$, строка будет равна $$$000$$$, потому что мудрецы $$$1$$$ и $$$3$$$ не знакомы, $$$3$$$ и $$$2$$$ не знакомы, $$$2$$$ и $$$4$$$ не знакомы.