← 返回题目列表

Codeforces · 2062/H

H. 银河发电机

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

在二维宇宙中,一颗恒星可以用二维平面上的点 $$$(x,y)$$$ 来表示。两颗星直接相连当且仅当它们的 $$$x$$$ 或 $$$y$$$ 坐标相同,并且它们之间的线段上没有其他星。将星系定义为由直接或间接(通过其他恒星)连接的恒星组成的连接组件。

对于一组恒星,其值定义为执行以下操作任意(可能为零)次后可获得的最小星系数:在每次操作中,您可以选择一个没有恒星的点$$$(x,y)$$$。如果一个星星在此处创建后可以直接连接到至少 $$$3$$$ 星星,那么您就在这里创建了一个星星。

给你一个 $$$n\times n$$$ 矩阵 $$$a$$$,由 $$$0$$$ 和 $$$1$$$ 组成,描述一组 $$$S$$$ 恒星。当且仅当 $$$a_{x,y}=1$$$ 时,$$$(x,y)$$$ 处有一颗星。计算 $$$S$$$ 的所有非空子集的值的总和(以 $$$10^9 + 7$$$ 为模)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 14$$$) — 矩阵 $$$a$$$ 的大小。

然后是 $$$n$$$ 行;第 $$$i$$$ 行包含长度为 $$$n$$$ 的字符串 $$$a_i$$$ — 矩阵 $$$a$$$ 的第 $$$i$$$ 行。

保证所有测试用例的$$$2^n$$$总和不超过$$$2^{14}$$$。

输出

对于每个测试用例,输出 $$$S$$$ 的所有非空子集的值的模 $$$10^9 + 7$$$ 的总和。

示例

输入 #1

8
1
0
2
01
10
3
010
000
101
4
0110
1001
1001
0110
11
11111110111
10000010010
10111010011
10111010011
10111010001
10000010000
11111110101
00000000111
11011010011
10010101100
11101010100
11
11011111110
10010000010
00010111010
10010111010
01010111010
11010000010
01011111110
11000000000
01010000010
01000111100
00000001010
11
11010101001
11001010100
00000000110
11111110010
10000010010
10111010110
10111010111
10111010010
10000010110
11111110100
00000000000
3
111
100
111

输出 #1

0
4
9
355
593092633
438667113
922743932
155

注意

在第一个测试用例中,$$$S$$$ 为空。 $$$S$$$ 没有非空子集。所以答案是$$$0$$$。

在第二个测试用例中,$$$S = \{(1,2),(2,1)\}$$$。 $$$S$$$ 有 $$$3$$$ 非空子集。

- $$$\{(1,2)\}$$$ 和 $$$\{(2,1)\}$$$ — 集合中只有一颗恒星,形成 $$$1$$$ 星系。
- $$$\{(1,2),(2,1)\}$$$ — 集合中的两颗恒星未连接,形成 $$$2$$$ 星系。

所以答案是$$$1+1+2=4$$$。

在第三个测试用例中,$$$S = \{(1,2),(3,1),(3,3)\}$$$。 $$$S$$$ 有 $$$7$$$ 非空子集。

- $$$\{(1,2)\}$$$、$$$\{(3,1)\}$$$ 和 $$$\{(3,3)\}$$$ — 集合中只有一颗恒星,形成 $$$1$$$ 星系。
- $$$\{(1,2),(3,1)\}$$$ 和 $$$\{(1,2),(3,3)\}$$$ — 集合中的两颗恒星没有连接,形成 $$$2$$$ 星系。
- $$$\{(3,1),(3,3)\}$$$ — 集合中的两颗恒星相连,形成 $$$1$$$ 星系。
- $$$\{(1,2),(3,1),(3,3)\}$$$ — 最初,恒星 $$$(1,2)$$$ 不在由 $$$(3,1)$$$ 和 $$$(3,3)$$$ 形成的星系中。您可以进行操作,在 $$$(3,2)$$$ 处创建一颗恒星,连接到这三颗恒星,形成 $$$1$$$ 星系。

所以答案是$$$1+1+1+2+2+1+1=9$$$。