問題一覧 > 通常問題

No.1327 グラフの数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 26
作問者 : 👑 testestest / テスター : 37zigen
1 ProblemId : 4982 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-09-03 18:46:37

問題文

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

入力

N

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

出力

∑M(−1)Mf(N,M) を mod109+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≠2,3 のとき f(N,M)=0 であることから、答えは (−1)2f(3,2)+(−1)3f(3,3)=3−1=2 となります。

サンプル2
入力
930372020
出力
930372019

サンプル3
入力
1000000007
出力
1000000006

サンプル4
入力
1000000007000000000000000000000000000000000000000000000000000000000000000000001
出力
0

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

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