頂点 \(i, j\) (\(i \lt j\)) 間に道があるとすると, 頂点 \(i\) への行き方の数 \(P(i)\) は,

\[P(i) = \sum_{j=1}^{i-1} P(j)\]

となる. これは

\[P(1) = 1 \\ P(2) = 1 \\ P(i) = 2P(i-1)\]

となるので, \(i \geq 2\) において \(P(i) = 2^{i-2}\) となる.

\(K \leq 10^9 \lt 2^{30}\) なので, \(N=31\) までこれで計算する.

あとは \(K\) を2進数で表し (\(2^k\) の和で表し), \(i\) 番目のビットが立っているときは頂点 \(i+1\) から頂点 \(32\) への辺を追加すればいい.