BZOJ4671 异或图

Luogu
IDLGP10591
Time1000ms
Memory512MB
DifficultyP6
O2优化容斥原理线性基
定义两个结点数相同的图 $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$ 有多少个子集的异或为一个连通图? ## Input 第一行为一个整数 $s$,表示图的个数。 接下来每一行一个二进制串,第 $i$ 行的二进制串为 $g_i$,其中 $g_i$ 是原图通过以下伪代码转化得到的。图的结点从 $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 ``` ## Output 输出一行一个整数,表示方案数。 [samples] ## Background 题目来自原 BZOJ,我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益,可联系我们。 ## Note 对于 $100\%$ 的数据,$2\leq n\leq 10$,$1\leq s\leq 60$。
Samples
Input #1
3 
1 
1 
0
Output #1
4
API Response (JSON)
{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments