AtCoder Regular Contest 044 B : 最短路問題

まず、深さについて分けて考えると、
前段（個数n）と次段（個数m）の組み合わせの数について考える問題になる。

前段は、完全グラフ $K_n$ のように辺を取りうる。
その辺の中で自由に選んでいいので、

$\begin{eqnarray} 2^{\frac{N(N-1)}{2}} \end{eqnarray}$

となる。

次段には、前段から辺を引っ張ってこなくてはならず、
かつ次段のすべてに辺がつながっている状態でないといけない。

次段について着目すると、一つのノードは
前段に1つ以上の自由な辺のつなげ方をすれば、条件を満たせる。
これがm個あるので、

$\begin{eqnarray} (2^n - 1) ^ m \end{eqnarray}$

これをかけていけば答えになる。
あとは、あり得ない入力に対して0を出力するようにする。

考察のメモ

f:id:arukuka:20161031140525j:plain

f:id:arukuka:20161031140534j:plain

終わってみればめっちゃシンプルな問題だけど、
かなりてこずった・・・。
嘘考察を生やしてはそれを見つけて新しい考察を考える・・・。

でも、自力で解けてよかった。