No.1877 Becoming a Line Graph Myself
タグ : / 解いたユーザー数 64
作問者 :
37zigen
/ テスター :
testestest
👑 Problem Statement
Among simple undirected graphs $G$ with $N$ vertices, find the number of those whose line graph $L(G)$ is isomorphic to the graph itself, up to isomorphism, modulo $10^9+7$.
The line graph $L(G)$ is the graph defined as follows.
- $V(L(G)) = E(G)$
- $E(L(G)) = \{\{a, b\} : a, b \in E(G), |a \cap b| = 1\}$
The following is an example of isomorphic graphs. Graphs $G$ for which there exists a correspondence of vertices that preserves the adjacency relations, like these, should be regarded as identical when counting.
Input
$N$
$1 \leq N \leq 1000$
Output
Among simple undirected graphs $G$ with $N$ vertices, output the number of those whose line graph $L(G)$ is isomorphic to the graph itself, up to isomorphism, modulo $10^9+7$. Print a newline at the end.
Sample
Sample 1
Input
100
Output
4372211
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。