19098번 - Vertex covers 다국어

A vertex cover of an undirected simple graph $G = (V, E)$ is a subset $S \subseteq V$ such that for every $(u, v) \in E$ we have $u \in S$ or $v \in S$. The size a of vertex cover $S$ is defined as $|S|$.

You need to determine what is the number of simple graphs with $n$ vertices whose smallest vertex cover has size exactly $k$.

Two graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ are considered different if and only if there exist two vertices $u, v \in V$ ($u\neq v$) such that edge $(u, v)$ belongs to exactly one of the sets $E_1$, $E_2$.

Since the answer can be very big, it suffices to print it modulo $2$.

The first line of the input contains an integer $q$ ($1 \le q \le 2^{8}$) denoting the number of queries. The following $q$ lines contain descriptions of individual queries. The $i$-th of them contains the description of the $i$-th query: two integers $n_i$ and $k_i$ ($1 \le n_i < 2^{8}$, $0 \le k_i < n_i$), denoting the number of vertices of $G$ (i.e., $|V|=n_i$) and the desired size of the smallest vertex cover, respectively.

You should print $q$ lines. The $i$-th of them should contain either $0$ or $1$ -- the answer to the $i$-th query.

• In the first query $V$ has size $3$. Simple graphs with vertices set $V$ with the smallest vertex cover of size $1$ are exactly the graphs with either one or two edges. There are six of them.
• In the second query, if a graph on $5$ vertices has the smallest vertex cover of size $4$, it has to be a clique.