P10591 BZOJ4671 XOR Graph

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem setter(s) who authorized BZOJ to use the problem. If you are the copyright owner and believe that we have infringed your rights, please contact us.

Define the XOR of two graphs $G_1$ and $G_2$ with the same number of vertices as a new graph $G$. If the total number of occurrences of $(u, v)$ in $G_1$ and $G_2$ is $1$, then the edge $(u, v)$ is in $G$; otherwise, this edge is not in $G$. Now you are given $s$ graphs $G_{1\sim s}$ with the same number of vertices, $S=\{G_1,G_2,\dots,G_s\}$. How many subsets of $S$ have an XOR that is a connected graph?

The first line contains an integer $s$, representing the number of graphs. Each of the following lines contains a binary string. The binary string on line $i$ is $g_i$, where $g_i$ is obtained from the original graph by the following pseudocode. The vertices are numbered starting from $1$, and let the number of vertices be $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 one line containing an integer, representing the number of valid ways.

For $100\%$ of the data, $2\leq n\leq 10$ and $1\leq s\leq 60$. Translated by ChatGPT 5