← 返回题目列表

Codeforces · 1326/F2

F2. 智者(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。不同的是智者数量的限制和时间的限制。只有解决了该任务的所有版本,您才可以进行黑客攻击。

$$$n$$$ 智者生活在一座美丽的城市。他们中有些人互相认识。

对于每个 $$$n!$$$ 可能的排列 $$$p_1, p_2, \ldots, p_n$$$ 的智者,让我们生成一个长度为 $$$n-1$$$ 的二进制字符串:对于每个 $$$1 \leq i < n$$$ 设置 $$$s_i=1$$$ if $$$p_i$$$ 和$$$p_{i+1}$$$ 彼此认识,否则$$$s_i=0$$$。

对于所有可能的 $$$2^{n-1}$$$ 二进制字符串,找到产生该二进制字符串的排列数。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 18)$$$ — 城市中智者的数量。

接下来的 $$$n$$$ 行每行包含一个长度为 $$$n$$$ 的二进制字符串,如果智者 $$$i$$$ 认识智者 $$$j$$$,则第 $$$i$$$ 字符串的第 $$$j$$$ 个字符等于“1”,否则等于“0”。

可以保证,如果第 $$$i$$$ 人认识第 $$$j$$$ 人,则第 $$$j$$$ 人认识第 $$$i$$$ 人,并且没有人认识自己。

输出

打印 $$$2^{n-1}$$$ 空格分隔的整数。对于每个 $$$0 \leq x < 2^{n-1}$$$:

- 让我们考虑一个长度为 $$$n-1$$$ 的字符串 $$$s$$$,使得 $$$s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$$$ 对于所有 $$$1 \leq i \leq n - 1$$$。
- 第 $$$(x+1)$$$ 个数字应等于 $$$s$$$ 所需的答案。

示例

输入 #1

3
011
101
110

输出 #1

0 0 0 6

输入 #2

4
0101
1000
0001
1010

输出 #2

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$$$也不认识彼此。