CF1326F2 Wise Men (Hard Version)

这是该问题的困难版本。不同之处在于智者人数的限制和时间限制。只有在所有版本的此任务都被解决后，才能进行 hack。 有 $n$ 位智者居住在一座美丽的城市中。他们中的一些人彼此认识。 对于智者的每一种 $n!$ 种排列 $p_1, p_2, \ldots, p_n$，我们可以生成一个长度为 $n-1$ 的二进制字符串：对于每个 $1 \leq i < n$，如果 $p_i$ 和 $p_{i+1}$ 彼此认识，则设 $s_i=1$，否则 $s_i=0$。 对于所有可能的 $2^{n-1}$ 个二进制字符串，求有多少种排列会生成该二进制字符串。

输入的第一行包含一个整数 $n$（$2 \leq n \leq 18$）——城市中智者的数量。 接下来的 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串，其中第 $i$ 行的第 $j$ 个字符等于 '1' 当且仅当第 $i$ 位智者认识第 $j$ 位智者，否则为 '0'。 保证如果第 $i$ 位智者认识第 $j$ 位智者，则第 $j$ 位智者也认识第 $i$ 位智者，且没有人认识自己。

输出 $2^{n-1}$ 个用空格分隔的整数。对于每个 $0 \leq x < 2^{n-1}$： - 设有一个长度为 $n-1$ 的字符串 $s$，其中 $s_i = \left\lfloor \frac{x}{2^{i-1}} \right\rfloor \bmod 2$，对所有 $1 \leq i \leq n-1$。 - 第 $x+1$ 个数应等于对应 $s$ 的排列数量。

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