CF1326F2.Wise Men (Hard Version)

This is the hard version of the problem. The difference is constraints on the number of wise men and the time limit. You can make hacks only if all versions of this task are solved.

$n$ wise men live in a beautiful city. Some of them know each other.

For each of the $n!$ possible permutations $p_1, p_2, \ldots, p_n$ of the wise men, let's generate a binary string of length $n-1$: for each $1 \leq i \lt n$ set $s_i=1$ if $p_i$ and $p_{i+1}$ know each other, and $s_i=0$ otherwise.

For all possible $2^{n-1}$ binary strings, find the number of permutations that produce this binary string.

这是该问题的困难版本。区别在于对智者人数和时间限制的约束。仅当该题的所有版本均被解决后，你才可以进行 hack。

一座美丽的城市中住着 $n$ 位智者。其中一些人彼此相识。

对于 $n!$ 种可能的智者排列 $p_1, p_2, \ldots, p_n$ 中的每一种，我们生成一个长度为 $n-1$ 的二进制字符串：对每个 $1 \leq i \lt n$，若 $p_i$ 与 $p_{i+1}$ 彼此相识，则令 $s_i = 1$；否则令 $s_i = 0$。

对所有 $2^{n-1}$ 种可能的二进制字符串，求出能生成该字符串的排列数目。

The first line of input contains one integer $n$ ($2 \leq n \leq 18)$ — the number of wise men in the city.

The next $n$ lines contain a binary string of length $n$ each, such that the $j$-th character of the $i$-th string is equal to '1' if wise man $i$ knows wise man $j$, and equals '0' otherwise.

It is guaranteed that if the $i$-th man knows the $j$-th man, then the $j$-th man knows $i$-th man and no man knows himself.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 18$），表示城市中智者的数量。

接下来的 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串；其中第 $i$ 行的第 $j$ 个字符为 '1'，表示第 $i$ 位智者认识第 $j$ 位智者；否则为 '0'。

保证：若第 $i$ 位智者认识第 $j$ 位智者，则第 $j$ 位智者也认识第 $i$ 位智者，且任何人都不认识自己。

Print $2^{n-1}$ space-separated integers. For each $0 \leq x \lt 2^{n-1}$:

• Let's consider a string $s$ of length $n-1$, such that $s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$ for all $1 \leq i \leq n - 1$.
• The $(x+1)$-th number should be equal to the required answer for $s$.

输出 $2^{n-1}$ 个空格分隔的整数。对每个 $0 \leq x \lt 2^{n-1}$：

• 考虑一个长度为 $n-1$ 的字符串 $s$，其中对所有 $1 \leq i \leq n - 1$，有 $s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$。
• 第 $(x+1)$ 个数应等于该字符串 $s$ 对应的所求答案。

In the first test, each wise man knows each other, so every permutation will produce the string $11$.

In the second test:

• If $p = {1, 2, 3, 4}$, the produced string is $101$, because wise men $1$ and $2$ know each other, $2$ and $3$ don't know each other, and $3$ and $4$ know each other;
• If $p = {4, 1, 2, 3}$, the produced string is $110$, because wise men $1$ and $4$ know each other, $1$ and $2$ know each other and $2$, and $3$ don't know each other;
• If $p = {1, 3, 2, 4}$, the produced string is $000$, because wise men $1$ and $3$ don't know each other, $3$ and $2$ don't know each other, and $2$ and $4$ don't know each other.

在第一个测试中，每位智者都彼此认识，因此每个排列都会生成字符串 $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$ 彼此不认识。