这是问题的简单版本。不同的是智者数量的限制和时间的限制。只有解决了该任务的所有版本,您才可以进行黑客攻击。
$$$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 14)$$$ — 城市中智者的数量。
接下来的 $$$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$$$也不认识彼此。