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