問題一覧 > 通常問題

No.1327 グラフの数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 20
作問者 : testestesttestestest / テスター : 37zigen37zigen
0 ProblemId : 4982 / 出題時の順位表
問題文最終更新日: 2020-09-03 18:46:37

問題文

頂点に $1$ ~ $N$ の番号がついた $N$ 頂点 $M$ 辺単純連結無向グラフの個数を $f(N,M)$ とします。
$N$ が与えられるので、$\sum_M (-1)^Mf(N,M)$ を $\bmod 10^9+7$ で求めてください。
なお、$N$ を固定するごとに、$f(N,M)$ は有限個の $M$ を除いて0になるので、この無限和は well-definedです。

入力

$N$

$N\geq 2$
入力ファイルはとてつもなく大きい可能性があります。

出力

$\sum_M (-1)^Mf(N,M)$ を $\bmod 10^9+7$ で求めてください。
最後に改行してください。

サンプル

サンプル1
入力
3
出力
2

3頂点2辺の単純連結無向グラフは 1-2-3、2-3-1、3-1-2、の3種類があるので、$f(3,2)=3$ です。
また、$f(3,3)=1$ であることと、$M\neq2,3$ のとき $f(N,M)=0$ であることから、答えは $(-1)^2 f(3,2)+(-1)^3 f(3,3)=3-1=2$ となります。

サンプル2
入力
930372020
出力
930372019

サンプル3
入力
1000000007
出力
1000000006

サンプル4
入力
1000000007000000000000000000000000000000000000000000000000000000000000000000001
出力
0

パターン! パターン見えてきたよ!

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