{"problem":{"name":"BZOJ4671 异或图","description":{"content":"定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$，其中如果 $(u,v)$ 在 $G_1$ 与 $G_2$ 中的出现之和为 $1$，那么边 $(u,v)$ 在 $G$ 中，否则这条边不在 $G$ 中。 现在给定 $s$ 个结点数相同的图 $G_{1\\sim s}$，$S=\\{G_1,G_2,\\dots,G_s\\}$，请问 $S$ 有多少个子集的异或为一个连通图？","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10591"},"statements":[{"statement_type":"Markdown","content":"定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$，其中如果 $(u,v)$ 在 $G_1$ 与 $G_2$ 中的出现之和为 $1$，那么边 $(u,v)$ 在 $G$ 中，否则这条边不在 $G$ 中。\n\n现在给定 $s$ 个结点数相同的图 $G_{1\\sim s}$，$S=\\{G_1,G_2,\\dots,G_s\\}$，请问 $S$ 有多少个子集的异或为一个连通图？\n\n## Input\n\n第一行为一个整数 $s$，表示图的个数。\n\n接下来每一行一个二进制串，第 $i$ 行的二进制串为 $g_i$，其中 $g_i$ 是原图通过以下伪代码转化得到的。图的结点从 $1$ 开始编号，下面设结点数为 $n$。\n\n```\nAlgorithm 1 Print a graph G = (V, E)\n\nfor i = 1 to n do\n    for j = i + 1 to n do\n        if G contains edge (i, j) then\n            print 1\n        else\n            print 0\n        end if\n    end for\nend for\n```\n\n## Output\n\n输出一行一个整数，表示方案数。\n\n[samples]\n\n## Background\n\n题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。\n\n## Note\n\n对于 $100\\%$ 的数据，$2\\leq n\\leq 10$，$1\\leq s\\leq 60$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10591","tags":["O2优化","容斥原理","线性基"],"sample_group":[["3 \n1 \n1 \n0","4"]],"created_at":"2026-03-03 11:09:25"}}