#P4671. 异或图

    ID: 3805 传统题 2000ms 256MiB 尝试: 757 已通过: 239 难度: 9 上传者: 标签>CF2600省选/NOI-容斥原理线性基秩判定回溯搜索对称性去重第二类 Stirling 数高精度加法高精度乘法斯特林数反演

异或图

题目描述

定义两个结点数相同的图 G1G_1 与图 G2G_2 的异或为一个新的图 GG,其中如果 (u,v)(u, v) 在 G1G_1 与 G2G_2 中的出现次数之和为 11,那么边 (u,v)(u, v) 在 GG 中,否则这条边不在 GG 中。

现在给定 ss 个结点数相同的图 G1∼sG_{1 \sim s}, S={G1,G2,…,Gs}S = \{G_1, G_2, \dots, G_s\},请问 SS 有多少个子集的异或为一个连通图?

输入格式

第一行为一个整数 ss,表图的个数.

接下来每一个二进制串,第 ii 行的二进制串为 gig_i,其中 gig_i 是原图通过以下伪代码转化得到的。图的结点从 11 开始编号,下面设结点数为 nn。

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

输出格式

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

输入输出样例

样例输入 #1

3 
1 
1 
0

样例输出 #1

4

数据范围与约定

对于 100% 的数据,2≤n≤102 ≤ n ≤ 10,1≤s≤601 ≤ s ≤ 60。