bzoj#P4671. 异或图
异或图
题目描述
定义两个结点数相同的图 与图 的异或为一个新的图 ,其中如果 在 与 中的出现次数之和为 ,那么边 在 中,否则这条边不在 中。
现在给定 个结点数相同的图 , ,请问 有多少个子集的异或为一个连通图?
输入格式
第一行为一个整数 ,表图的个数.
接下来每一个二进制串,第 行的二进制串为 ,其中 是原图通过以下伪代码转化得到的。图的结点从 开始编号,下面设结点数为 。
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% 的数据,,。