UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4671. 异或图

Statistics 下载数据

Description

定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与
G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.
现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异
或为一个连通图?

Input

第一行为一个整数s, 表图的个数.
接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得
到的. 图的结点从 1 开始编号, 下面设结点数为 n.
Algorithm 1 Print a graph G = (V, E)
for i = 1 to n do
for j = i + 1 to n do
if G contains edge (i, j) then
print 1
else
print 0
end if
end for
end for
 2 ≤ n ≤ 10,1 ≤ s ≤ 60.

Output

输出一行一个整数, 表示方案数

Sample Input

3
1
1
0

Sample Output

4

Hint

Source