No.1327 Counting Graphs
タグ : / 解いたユーザー数 26
作問者 :
testestest
/ テスター :
37zigen
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もしくは右上の雲マークをクリックしてアカウントを作成してください。