問題一覧 > 通常問題

No.1877 Becoming a Line Graph Myself

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 64
作問者 : 37zigen / テスター : testestest 👑 cologne
お気に入りにしたユーザー ProblemId : 4625 / 自分の提出
問題文最終更新日: 2022-03-19 02:07:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 336 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。