19467번 - Graph Coloring 2 다국어

문제

You are given an undirected graph with $n$ vertices numbered 0ドル$ through $n - 1$. Obviously, the set of vertices have 2ドル^n - 1$ non-empty subsets. For a non-empty subset $S,ドル a proper coloring of $S$ is a way to assign each vertex in $S$ a color, so that no two vertices in $S$ with the same color are directly connected by an edge. Assume we used $k$ different kinds of colors in a proper coloring. The chromatic number of subset $S$ is the minimum possible $k$ among all the proper colorings of $S$.

Now your task is to compute the chromatic number of every non-empty subset of $n$ vertices.

입력

The first line contains an integer $T$. Then $T$ test cases follow.

The first line of each test case contains an integer $n$. Each of then next $n$ lines contains a string consisting of '0' and '1'. For 0ドル \le i \le n - 1$ and 0ドル \le j \le n - 1,ドル if the $j$-th character of the $i$-th line is '1', then vertices $i$ and $j$ are directly connected by an edge, otherwise they are not directly connected.

The $i$-th character of the $i$-th line is always '0'. The $i$-th character of the $j$-th line is always the same as the $j$-th character of the $i$-th line.

For all test cases, 1ドル \le n \le 18$. There are no more than 100ドル$ test cases with 1ドル \le n \le 10,ドル no more than 3ドル$ test cases with 11ドル \le n \le 15,ドル and no more than 2ドル$ test cases with 16ドル \le n \le 18$.

출력

For each test case, print an integer on a separate line. This integer is determined as follows: We define the identity number of subset $S$ as $\mathit{id} (S) = \sum_{v \in S} 2^v$. Let the chromatic number of $S$ be $f_{\mathit{id} (S)}$. You need to output $$\left(\sum\limits_{\mathit{id} (S) = 1}^{2^n - 1} f_{\mathit{id} (S)} \cdot 233^{\mathit{id} (S)}\right) \bmod 2^{32}\text{.}$$

제한

힌트

For the first test case, $ans[1..15] = \{1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2, 3\}$.