問題一覧 > 通常問題

No.1327 Counting Graphs

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : testestest / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 4982 / 自分の提出
問題文最終更新日: 2020-09-03 18:46:37
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
Advent Calendar Contest 2020 (順位表) の他の問題:

Problem Statement

Let $f(N,M)$ be the number of simple connected undirected graphs with $N$ vertices and $M$ edges, whose vertices are numbered $1$ to $N$.
Given $N$, find $\sum_M (-1)^Mf(N,M)$ modulo $\bmod 10^9+7$.
Note that for each fixed $N$, $f(N,M)$ is 0 for all but finitely many $M$, so this infinite sum is well-defined.

Input

$N$

$N\geq 2$
The input file may be extremely large.

Output

Find $\sum_M (-1)^Mf(N,M)$ modulo $\bmod 10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
3
Output
2

There are 3 simple connected undirected graphs with 3 vertices and 2 edges: 1-2-3, 2-3-1, and 3-1-2, so $f(3,2)=3$.
Also, since $f(3,3)=1$ and $f(N,M)=0$ for $M\neq2,3$, the answer is $(-1)^2 f(3,2)+(-1)^3 f(3,3)=3-1=2$.

Sample 2
Input
930372020
Output
930372019

Sample 3
Input
1000000007
Output
1000000006

Sample 4
Input
1000000007000000000000000000000000000000000000000000000000000000000000000000001
Output
0

A pattern! I can see a pattern emerging!

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。